堆排序 C语言实现

堆排序

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

O(n $log_2$ n)

空间复杂度

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;
}