顾名思义，堆排序就是利用堆的性质进行的选择排序

堆

堆是一棵顺序存储的完全二叉树
其中每个根结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个根结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。

完全二叉树性质

设当前元素为数组的第i个元素，那么，
(1) 它的左孩子结点是：2i + 1;
(2) 它的右孩子结点是：2i + 2;
(3) 它的父结点是：(i-1) / 2;
(4)从下往上第一个非叶子节点：(length / 2) - 1;

算法思路

1. 构造初始堆(从由下至上第一个非叶子节点开始)；
2. 交换首尾元素；
3. 数组长度减一，把剩下的元素重新调整为大根堆；
4. 重复2、3直至剩下最后一个元素结束。

构造堆示意图

构造堆示意图

排序过程

排序过程

C代码

void heapAdjust(int *a, int parent, int length) {
    int temp = a[parent];
    int child = 2 * parent + 1;//先看左孩子
    
    while (child < length) {
        // 如果有右孩子且右孩子大于左孩子,那么选取右孩子
        if (child + 1 < length && a[child + 1] > a[child]) {
            child++;
        }
        
        // 如果父节点大于子节点则跳出循环
        if (temp > a[child]) break;
        
        // 父节点小于子节点，给父节点赋值
        a[parent] = a[child];
        
        // 把孩子节点变为父节点继续往下遍历比较
        parent = child;
        child = 2 * parent + 1;
    }
    // 遍历完成
    a[parent] = temp;
}

void heapSort(int a[], int length) {
    // 初始化堆
    for (int i = length / 2 - 1; i >=0; i--) {
        heapAdjust(a, i, length);
    }
    // 进行n-1次循环，完成排序
    for (int i = length - 1; i > 0; i--) {
        //交换首尾元素
        int temp = a[i];
        a[i] = a[0];
        a[0] = temp;
        
        // 调整堆
        heapAdjust(a, 0, i);
    }
}

复杂度