堆排序

堆排序( Heap Sort )只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个
存储空间。

堆的定义如下: n 个元素的序列 { k₁, k₂ ,..., k_n }当且仅当满足下关系时,称之为堆。

若将和此序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此,若序列 { k₁, k₂ ,..., k_n } 是堆,则堆顶元素(或完全二叉树的根)必为序列中 n 个元素的最小值(或最大值)。

若在输出堆顶的最小值之后,使得剩余 n - 1 个元素的序列重又建成一个堆,则得到n 个元素中的次小值。如此反复执行,便能得到一个有序序列,这个过程称之为堆排序。

源码如下：

#include <iostream>
#define SPACE 0x100
// 检测左边的数是否小于右边的，如果是，结果为 1 ，否则 0。
#define LT(left, right) (left < right ? 1 : 0)

// 检测左边的数是否大于右边的，如果是，结果为 1 ，否则 0。
#define GT(left, right) (left > right ? 1 : 0)

//#define DESCENDING_ORDER       //去掉注释，则使用降序排列

using namespace std;

struct Data
{
    int key;
};

struct SqList
{
    Data r[SPACE];
    int length;
};

typedef SqList HeapType; // 堆采用顺序表存储表示

// 输出数组
void print(HeapType &L, int low, int high)
{
    cout << "[ ";
    for (int i = low; i <= high; i++)
    {
        cout << L.r[i].key << ", ";
    }
    cout << "]" << endl;
}

// 已知 H.r[s .. m]中记录的关键字除 H. r[s].key 之外均满足堆的定义,本函数调整 H.r[s]
// 的关键字,使 H.r[s .. m]成为一个大顶堆(对其中记录的关键字而言)
void HeapAdjust(HeapType &H, int s, int m)
{
    Data rc = H.r[s];

    //沿 key 较大的孩子结点向下筛选
    for (int j = 2 * s; j <= m; j *= 2)
    {
        // j 为 key 较大的记录的下标
#ifndef DESCENDING_ORDER
        if (j < m && LT(H.r[j].key, H.r[j + 1].key))
        {
            ++j;
        }
#else
        if (j < m && GT(H.r[j].key, H.r[j + 1].key))
        {
            ++j;
        }
#endif

        // rc 应插入在位置 s 上
#ifndef DESCENDING_ORDER
        if (!LT(rc.key, H.r[j].key))
        {
            break;
        }
#else
        if (!GT(rc.key, H.r[j].key))
        {
            break;
        }
#endif

        H.r[s] = H.r[j];
        s = j;
    }
    H.r[s] = rc; // 插入
}

// 对顺序表 H 进行堆排序。
void HeapSort(HeapType &H)
{
    // 这里建立初始堆
    // 默认把 H.r[1 ... H.length]建成 大顶堆
    // 如果定义了 DESCENDING_ORDER 则建成 小顶堆
    for (int i = H.length / 2; i > 0; --i)
    {
        HeapAdjust(H, i, H.length);
    }

    cout << "初始堆  ：";
    print(H, 1, H.length);

    for (int i = H.length; i > 1; --i)
    {
        // 将堆顶记录和当前未经排序子序列 Hr[l ... i]中最后一个记录相互交换
        Data temp = H.r[1];
        H.r[1] = H.r[i];
        H.r[i] = temp;

        // 将 H.r[ l ... i-1 ]重新调整为 大顶堆
        // 如果定义了 DESCENDING_ORDER 则重新调整为 小顶堆
        HeapAdjust(H, 1, i - 1);
    }
}

int main()
{
    // 使用的书中的数据，可以参照书本进行调试
    HeapType heap = {0, 49, 38, 65, 97, 76, 13, 27, 49};
    heap.length = 8;
    cout << "初始数据：";
    print(heap, 1, heap.length);

    HeapSort(heap);
    cout << "结果数据：";
    print(heap, 1, heap.length);

    return 0;
}

运行结果：

初始数据：[ 49, 38, 65, 97, 76, 13, 27, 49, ]
初始堆  ：[ 97, 76, 65, 49, 49, 13, 27, 38, ]
结果数据：[ 13, 27, 38, 49, 49, 65, 76, 97, ]

堆排序的关键字比较次数与元素初始排列次序是有关系的

因为进行堆排序的时候，如果第一次判断失败了，会直接返回，但是如果成功了的话，则会继续和他的子树进行判断，而元素初始排列次序会影响第一次判读的对错，使得堆排序的关键字比较次数与元素初始排列次序是有关。

资料来源：《数据结构》严蔚敏版