概述

堆排序是一种树形选择排序，在排序的过程中，将待排序的记录r[1...n]看作一棵完全二叉树的顺序存储结构。

特点

• 不稳定排序；
• 只能用于顺序结构，不能用于链式结构；
• 初始建堆比较次数较多，因此记录较少时不宜使用；
• 最坏时间复杂度O(nlogn)，当记录较多时较为高效；

过程

建初堆

要将一个无序序列调整为堆，就要将其所对应的完全二叉树中以每一个节点为根的子树都调整为堆。显然，只有一个节点的树必是堆，而在完全二叉树中，所有序号大于n/2的节点（层序遍历）都是叶子，因此以这些节点为根的子树均已是堆。这样，只需要用 筛选法 从最后一个分支节点n/2开始，依次将序号为n/2、n/2-1、...、1的节点为根的子树都调整为堆即可。

对于无序序列r[1...n]，从i = n/2开始，反复调用筛选法HeapAdjust(L, i, n)，依次将以r[i]、r[i-1]、...、r[1]为根的子树调整为堆。

void CreatHeap(SqList &L)
{ //把无序序列 L.r[1...n] 建成大根堆
    n = L.length();
    for (i = n / 2; i > 0; i--) //从后往前建立
    {
        HeapAdjust(L, i, n);
    }
}

调整堆

假设r[s+1...m]已经是堆，按 筛选法 将r[s...m]调整为以r[s]为根的堆，算法实现如下：

1. 从r[2s]和r[2s + 1]中选出关键字较大者，假设r[2s]的关键字较大，比较r[s]和r[2s]的关键字；
2. 若r[s].key >= r[2s].key，说明以r[s]为根的子树已经是堆，不必进行任何调整；
3. 若r[s].key < r[2s].key，交换r[s]和r[2s]。交换后，以r[2s+1]为根的子树仍是堆。如果以；r[2s]为根的子树不是堆，则重复上述过程，将以r[2s]为根的子树调整为堆，直至进行到叶子节点为止；

void HeapAdjust(SqList &L, int s, int m)
{
    auto rc = L.r[s];
    for (int j = 2 * s, j <= m; j *= 2) //沿key较大的孩子节点向下筛选
    {
        if (j < m && L.r[j].key < L.r[j + 1].key) //j为key较大的记录下标
            j++； //右孩子
        if (rc.key >= L.r[j].key) //如果当前子树已经是堆
            break;
        L.r[s] = L.r[j]; //交换
        s = j; //s下滤
    }
    L.r[c] = rc; //插入
}

堆排序

根据前面堆排序算法步骤的描述，可知堆排序就是将无序序列建成初堆以后，反复进行交换和堆调整。

void HeapSort(SqList &L)
{
    CreatHeap(L); //建立初始大根堆
    for (int i = L.length(); i > 1; i--)
    {
        swap(L.r[1], L.r[i]); //交换堆顶元素与未排序子序列 L.r[1...i] 中最后一个元素
        HeapAdjust(L, 1, i - 1); //将 L.r[1...i - 1] 调整为大根堆
    }
}