由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 (R1, R2 ...... Rn-1) 调整为新堆，然后再次将 R[1] 与无序区最后一个元素交换，得到新的无序区 (R1, R2 .... Rn-2) 和新的有序区 (Rn-1, Rn)。不断重复此过程，直到有序区的元素个数为 n - 1，则整个排序过程完成。
实现
// 堆排序 const heapSort = array => { console.time('堆排序耗时'); // 初始化大顶堆，从第一个非叶子结点开始 for (let i = Math.floor(array.length / 2 - 1); i >= 0; i--) { heapify(array, i, array.length); } // 排序，每一次 for 循环找出一个当前最大值，数组长度减一 for (let i = Math.floor(array.length - 1); i > 0; i--) { // 根节点与最后一个节点交换 swap(array, 0, i); // 从根节点开始调整，并且最后一个结点已经为当前最大值，不需要再参与比较，所以第三个参数为 i，即比较到最后一个结点前一个即可 heapify(array, 0, i); } console.timeEnd('堆排序耗时'); return array; }; // 交换两个节点 const swap = (array, i, j) => { let temp = array[i]; array[i] = array[j]; array[j] = temp; }; // 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是： // 假设结点 i 以下的子堆已经是一个大顶堆，heapify 函数实现的 // 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。 // 后面将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点 // 都执行 heapify 操作，所以就满足了结点 i 以下的子堆已经是一大顶堆 const heapify = (array, i, length) => { let temp = array[i]; // 当前父节点 // j < length 的目的是对结点 i 以下的结点全部做顺序调整 for (let j = 2 * i + 1; j < length; j = 2 * j + 1) { temp = array[i]; // 将 array[i] 取出，整个过程相当于找到 array[i] 应处于的位置 if (j + 1 < length && array[j] < array[j + 1]) { j++; // 找到两个孩子中较大的一个，再与父节点比较 } if (temp < array[j]) { swap(array, i, j); // 如果父节点小于子节点:交换；否则跳出 i = j; // 交换后，temp 的下标变为 j } else { break; } } };测试
const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]; console.log('原始array:', array); const newArr = heapSort(array); console.log('newArr:', newArr); // 原始 array: [4, 6, 8, 5, 9, 1, 2, 5, 3, 2] // 堆排序耗时: 0.15087890625ms // newArr: [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]分析
第一，堆排序是原地排序算法吗 ？
整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。
第二，堆排序是稳定的排序算法吗 ？
因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。
所以，堆排序是不稳定的排序算法。
第三，堆排序的时间复杂度是多少 ？
堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。
最佳情况：T(n) = O(nlogn)。
最差情况：T(n) = O(nlogn)。
平均情况：T(n) = O(nlogn)。
动画
6. 排序算法的复杂性对比复杂性对比
名称 平均 最好 最坏 空间 稳定性 排序方式归并排序 O(n log n) O(n log n) O(n log n) O(n) Yes Out-place
快速排序 O(n log n) O(n log n) O(n2) O(logn) No In-place
希尔排序 O(n log n) O(n log2 n) O(n log2 n) O(1) No In-place
堆排序 O(n log n) O(n log n) O(n log n) O(1) No In-place
算法可视化工具
算法可视化工具 algorithm-visualizer
算法可视化工具 algorithm-visualizer 是一个交互式的在线平台，可以从代码中可视化算法，还可以看到代码执行的过程。
效果如下图。