堆排序 C语言实现

古城微笑少年丶 2022-12-22 13:30 168阅读 0赞

### 堆排序 ###

(Heap Sort) 是一种树形选择排序，在排序过程中，将待排序的记录Data\[1…n\]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩 子结点之间的内在关系，在当前无序的序列中选择关键字最大(或最小)的记录。

**时间复杂度**

O(n l o g 2 log\_2 log2n)

**空间复杂度**

O(1)

**算法特点：**

1 ) 是**不稳定**排序。  
2 ) 只能用于顺序结构，不能用于链式结构。  
3 ) 初始建堆所需的比较次数较多，因此记录数较少时不宜采用。堆排序在最坏情况下时间复杂度为O(nlog2n)，相对于快速排序最坏情况下的O(n2)而言是一个优点， 当记录较多时较为高效。

**完整代码：**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 100 //顺序表最大容量，可以自行加大 
    
    typedef struct 
    { 
    	int key;//关键字项 
    	char *otherinfo;//其他数据项 
    }ElemType;//记录类型 
    typedef struct
    { 
    	ElemType Data[MAXSIZE+1];//静态顺序表的数据域，这里Data[0]为空闲或者为哨兵单元 
    	int length;//顺序表的长度 
    }SqList;//顺序表 
    
    void InitList(SqList &L)//顺序表的初始化 
    { 
    	L.length = 0;//使顺序表长度归0，便是顺序表的初始化 
    }
    
    void CreateList(SqList &L)//顺序表的创建 
    { 
    	printf("请输入："); 
    	while(1)//建立一个死循环，循环终止条件是按了enter键 
    	{ 
    		L.length++;//顺序表长度加一 
    		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
    		{ 
    			printf("顺序表已满！\n");
    			return ;
    		}
    		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
    		if(getchar() == '\n')//循环终止条件 
    			break;
    	}
    }
    
    void InputList(SqList L)//顺序表的输出 
    { 
    	int i;//记录次数 
    	if(L.length == 0)//判断顺序表是否为空 ，若为空结束该函数 
    	{ 
    		printf("顺序表是空的！\n");
    		return ;
    	}
    	printf("打印为：");
    	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
    		printf("%d ",L.Data[i].key);	
    }
    
    void HeapAdjust(SqList &L,int s,int m)//假设Data[s+1…m]已是堆，将Data[s…m]调整为以Data[s]为根的大根堆 
    { //筛选法调整堆 
    	int j;
    	L.Data[0] = L.Data[s];
    	for(j=2*s;j<=m;j*=2)//沿key较大的孩子结点向下筛选 
    	{ 
    		if(j<m&&L.Data[j+1].key > L.Data[j].key)//j为key较大的记录的下标 
    			j++;
    		if(L.Data[0].key >= L.Data[j].key)//Data[0]应插入在位置s上 
    			break;
    		L.Data[s] = L.Data[j];
    		s = j;
    	}
    	L.Data[s] = L.Data[0];//插入 
    }
    void CreatHeap(SqList &L)//建初堆，把无序序列L.Data[1…n]建成大根堆 
    { 
    	int i;
    	for(i=L.length/2;i>0;i--)//反复调用HeapAdjust 
    		HeapAdjust(L,i,L.length);
    }
    void HeapSort(SqList &L)//对顺序表L进行堆排序 
    { 
    	int i;
    	CreatHeap(L);//把无序序列L.Data[1…L.length]建成大根堆 
    	for(i=L.length;i>1;i--)
    	{ 
    		L.Data[0] = L.Data[1];//将堆顶记录和当前未经排序子序列L.Data[1…i]中最后一个记录互换 
    		L.Data[1] = L.Data[i];
    		L.Data[i] = L.Data[0];
    		HeapAdjust(L,1,i-1);//将L.Data[1…i-1]重新调整为大根堆 
    	}
    }
    
    int main()
    { 
    	SqList L;
    	InitList(L);//初始化顺序表 
    	CreateList(L);//创建顺序表 
    	HeapSort(L);//堆排序 
    	InputList(L);//打印排序后结果 
    	return 0;
    }

![在这里插入图片描述][20201120164213794.png_pic_center]  
（完）

[20201120164213794.png_pic_center]: /images/20221120/6349bf6725894845b46f511fd07b5978.png