C算法—堆排序

堆排序(Heap Sort)只需要一个记录大小的辅助空间
堆排序在最坏的情况下，其时间复杂度为O(nlog n),相对于快速排序来说，这是堆的最大优点。
堆是一棵完全二叉树，且树中不存在大于（小于）父节点的节点。
堆中的第i个元素大于或等于第2i个元素和第2i+1个元素。

---

自底向上的堆化

fixUp(Item* a, int k)
{
while(k>1 && less(a[k/2], a[k]))
...{
exch(a[k], a[k/2]);
k = k / 2; //向上找到父结点
}
}...

---

自顶向下的堆化

fixDown(Item* a, int k, int N)
{
int j;
while(2*k <= N)
...{
j = 2 * k;
if(j<N && less(a[j], a[j+1])) j++; //选择两个孩子中较大者，与a[k]比较
if(!less(a[k], a[j])) break; //局部满足堆条件，立即退出
exch(a[k], a[j]); //否则，交换
k = j;
}
}...

---

堆排序

void heapsort(Item* a, int l, int r)
{
int k, N = r-l+1; //N为待排元素的个数
for(k = N/2; k >= 1; k--) //建堆，从第一个非叶子节点开始
fixDown(a, k, N); //自顶向下的堆化
while(N > 1)
...{
exch(a[l], a[l+N-1]); //把第一个元素（最大）和最后一个元素交换
fixDown(a, 1, --N); //再自顶向下堆化
}
}...