排序 (六): 堆排序

[S-T-D]

• 思路
• 代码
• 复杂度
• 参考
   

思路

堆排序是一种基于优先队列（二叉堆）的排序方法。

如果对二叉堆不熟，可以查看我的另一篇博客：二叉堆。

稳定性：不稳定。

 

堆排序堆具体步骤：

以数组 [3, 10, 1, 6, 2, 8, 7] 为例

1. 构建堆

先将数组构建成最大堆：[10, 8, 3, 6, 7, 2, 1]。

使用完全二叉树表示为：

      10
    /   \
   8     3
  / \   / \
 6   7 2   1

2. 交换首尾元素

交换首尾的元素，使最大元素来到了数组末尾，相当于排定了最大值。

末尾元素来到了数组首位，打破了二叉堆的有序状态。

3. 缩减数组，下沉恢复秩序

对首元素执行下沉操作，使二叉堆恢复秩序，注意执行下沉操作的时候数组的范围，因为最后一个元素已经排定了，所以要缩减数组的范围。

4. 重复 2 和 3 步，直到数组起始位置

 

代码

/**
 * 堆排序
 * @param {number[]} tree 数组
 */
function heapSort(tree) {
    buildBinaryHeap(tree);
    sort(tree);

    /**
     * 排序
     * @param {number[]} heap 二叉堆
     */
    function sort(heap) {
        // 从末尾元素开始
        let endPosi = heap.length - 1;
        while (endPosi > 0) {
            // 和首元素交换
            swap(heap, 0, endPosi);
            // 对首元素下沉，恢复堆的秩序，同时缩减范围
            sink(heap, 0, --endPosi);
        }
    }

    /**
     * 构建二叉堆
     * @param {number[]} tree 数组
     */
    function buildBinaryHeap(tree) {
        const end = tree.length - 1;
        let posi = Math.floor((end - 1) / 2)
        // 从后往前计算出每一个有子节点的节点，对其进行下沉操作
        while (posi >= 0) {
            sink(tree, posi--);
        }
    }   

    /**
     * 对指定节点进行下沉
     * @param {number[]} heap 二叉堆
     * @param {number} posi 需要进行下层操作的元素的索引
     * @param {number} endPosi 末尾元素的索引
     */
    function sink(heap, posi, endPosi) {
        let index;
        // 如果左子节点满足，进入循环
        while ((index = 2 * posi + 1) <= endPosi) {
            // 选择左右子节点中较大的一个 
            if (index + 1 <= endPosi && heap[index] < heap[index + 1]) index++;
            // 如果父节点大于较大的子节点，结束循环
            if (heap[index] < heap[posi]) break;
            swap(heap, index, posi);
            posi = index;
        }
    }

    function swap(arr, i, j) {
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

复杂度

时间复杂度

令数组长度为 n。

在 二叉堆 中提到，构建堆的时间复杂度是 O(n)，下沉操作的时间复杂度是 logn，排序需要对 n 个节点执行下沉，所以总的时间复杂度是 nlogn。

空间复杂度

O(1)，没有使用额外的空间。

 

参考

• 《算法（第四版）》