堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构（通常堆是通过一维数组来实现的），并同时满足堆的性质：即子结点的键值总是小于（或者大于）它的父节点。
我们可以很容易的定义堆排序的过程：
1.创建一个堆
2.把堆顶元素(最大值)和堆尾元素互换
3.把堆的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
4.重复步骤2，直到堆的尺寸为1
分类--------------内部比较排序
数据结构----------数组
最差时间复杂度---- O(nlogn)
最优时间复杂度---- O(nlogn)
平均时间复杂度---- O(nlogn)
所需辅助空间------ O(1)
稳定性------------不稳定
#include
usingnamespacestd;
intheapsize;//堆大小
voidexchange(intA[],inti,intj)//交换A[i]和A[j]
{
inttemp = A[i];
A[i] = A[j];
A[j] = temp;
}
voidheapify(intA[],inti)//堆调整函数(这里使用的是最大堆)
{
intleftchild =2* i +1;//左孩子索引
intrightchild =2* i +2;//右孩子索引
intlargest;//选出当前结点与左右孩子之中的最大值
if(leftchild A[i])
largest = leftchild;
else
largest = i;
if(rightchild A[largest])
largest = rightchild;
if(largest != i)
{
exchange(A, i, largest);//把当前结点和它的最大(直接)子节点进行交换
heapify(A, largest);//递归调用，继续从当前结点向下进行堆调整
}
}
voidbuildheap(intA[],intn)//建堆函数
{
heapsize= n;
for(inti =heapsize/2-1; i >=0; i--)//对每一个非叶结点
heapify(A, i);//不断的堆调整
}
voidheapsort(intA[],intn)
{
buildheap(A, n);
for(inti = n -1; i >=1; i--)
{
exchange(A,0, i);//将堆顶元素(当前最大值)与堆的最后一个元素互换(该操作很有可能把后面元素的稳定性打乱,所以堆排序是不稳定的排序算法)
heapsize--;//从堆中去掉最后一个元素
heapify(A,0);//从新的堆顶元素开始进行堆调整
}
}
intmain()
{
intA[] = {5,2,9,4,7,6,1,3,8};//从小到大堆排序
intn =sizeof(A) /sizeof(int);
heapsort(A, n);
printf("堆排序结果：");
for(inti =0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
return0;
}
