堆排序是一种具有合并排序和插入排序共同优点的排序方法。它的时间复杂度为O(nlgn)，它也是一种原地排序算法：在任何时候，数组中只有常数个元素存储在输入数组以外。要介绍堆排序首先要介绍什么是堆。
1.建堆：堆数据结构是一种数组对象，它可以被视为一颗完全二叉树，如下图。右边数组表示的堆可以用左边的完全二叉树来表示，其中若父节点对应数组下标为i，则其左孩子对应数组下标为2*i，右孩子为2*i+1。
![\]()
![\]()
具体代码如下：<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+dm9pZCBidWlsZE1heEhlYXAoaW50IGFbXSAsIGludCBoZWFwU2l6ZSl7PGJyPgpmb3IoaW50IGkgPSBoZWFwU2l6ZS8yO2kgPj0gMTstLWkpPGJyPgptYXhfaGVhcGlmeShhLGksaGVhcFNpemUpOyAvL7G+0NC0+sLrtffTw21heF9oZWFwaWZ5uq/K/cC0saOz1tfutPO20dDU1sqjrL3Tz8LAtLvhvenJ3LW9oaNoZWFwU2l6Zc6qttG089ChoaM8YnI+Cn08L3A+CjxwPjIusaOz1rj5ttHQ1NbKo7q908/CwLS96cnctPO4+bbR0+vQobj5ttG1xMf4sfCho7TzuPm20cSzuPa92rXjtcQmIzIwNTQwO9futuDKx7rNxuS4uL3atePSu9H5tPOho9ChuPm20bXE1+nWr7jVusPP4Le0oaPU2rbRxcXQ8tbQztLDx8q508O1xMrHtPO4+bbRoaPOqsHLsaOz1rTzuPm20bXE0NTWyqOsztLDx7zZyei008/CserOqmm1xMr91+nUqsvYv6rKvKOsvavG5CYjMjA1NDA70+vL/LXE1/O6otfTus3T0rqi19PP4LHIvc+jrNXSs/bX7rTzJiMyMDU0MDu21NOmtcTPwrHqbGFyZ2VzdKOsyOe5+2xhcmdlc3THobrD0+tpz+C1yKOs1PLLtcP3vdq142mxo7PWwcvX7rTzttHQ1NbKoaO38dTyvbu7u8/CserOqmxhcmdlc3S6zWnL+bbU06a1xMr91+nUqsvYJiMyMDU0MDujrLKix9K21M/CserOqmxhcmdlc3S1xNSqy9i8zND4vfjQ0KGwsaOz1rj5ttHQ1NbKobG1xLLZ1/eho9Xiw7TLtb/JxNzT0NCpzKvIsbemyfq2r9DUo6zEx8O00rvG8MC0v7S/tNXiuPa5/bPMsMmjujxpbWcgc3JjPQ=="" alt="\">
可以看到图中节点值为4的节点的保持根堆性质过程。代码如下：
void max_heapify(int a[],int i,int heapSize){
int lindex = 2*i,rindex = 2*i + 1,largest = 0;
if(lindex <= heapSize && a[lindex-1] > a[i-1])//判断左孩子和节点i的值谁大，将大值得下标保存为largest
largest = lindex;
else
largest = i;
if(rindex <= heapSize && a[rindex-1] > a[largest-1])//判断右孩子和节点largest的值谁大
largest = rindex;
if(largest != i){//如果largest不等于i
swap(a[i-1] , a[largest-1]);//交换
max_heapify(a,largest,heapSize);//继续对下标为largest、大小为heapSize的节点进行“保持根堆性质”
}
}
以下是swap函数：
void swap(int& first , int& second){
int tem = 0;
tem = first;
first = second;
second = tem;
}
3.堆排序算法：我用一个图来直观表示吧！
![\]()
过程大致是将大根堆的根节点与最后一个叶子节点交换，然后缩小数组范围(即将heapSize减小)，将最大值排除掉，最后对新的根节点进行“保持堆性质方法”，依次类推，代码如下：
void heapSort(int a[] , int heapSize){
buildMaxHeap(a , heapSize);//建堆
for(int i = heapSize;i >= 2;--i){
swap(a[0] , a[i-1]);//将根节点与最后的叶子节点交换
--heapSize;//缩小堆范围
max_heapify(a,1,heapSize);//保持堆性质
}
}