JavaScript堆排序详解：算法原理、代码实现及性能分析64

堆排序 (Heap Sort) 是一种高效的排序算法，其时间复杂度为 O(n log n)，在最坏、平均和最佳情况下都保持一致。不同于快速排序和归并排序，堆排序是一种原地排序算法，不需要额外的空间来存储中间结果。本文将深入探讨 JavaScript 中的堆排序算法，包括其原理、代码实现以及性能分析，帮助大家更深入地理解这一经典算法。

一、堆排序的核心概念：堆

堆排序依赖于一种特殊的树形数据结构——堆。堆可以是最大堆，也可以是最小堆。最大堆满足以下性质：每个节点的值都大于或等于其子节点的值。最小堆则相反，每个节点的值都小于或等于其子节点的值。在堆排序中，我们通常使用最大堆。一个堆可以利用数组来实现，无需显式地构建树结构。假设数组索引从 0 开始，则对于任意节点 i，其左子节点的索引为 2i + 1，右子节点的索引为 2i + 2，父节点的索引为 ⌊(i - 1) / 2⌋。

二、堆排序算法步骤

堆排序算法主要分为两个步骤：构建堆和堆化排序。

1. 构建堆 (Build Heap): 此步骤将输入数组转换成一个最大堆。我们可以从数组的最后一个非叶子节点开始，自底向上地调整堆的结构，确保每个子树都满足最大堆的性质。这个过程可以递归实现，也可以迭代实现。迭代实现的效率更高，因为它避免了递归调用的开销。

2. 堆化排序 (Heapify): 此步骤反复从堆顶取出最大元素 (堆顶元素即为当前堆中的最大值)，将其与堆的最后一个元素交换，然后将堆的大小减 1。接着，我们调用 `heapify` 函数来调整新的堆顶，确保其仍然满足最大堆的性质。这个过程重复进行，直到堆为空，排序完成。

三、JavaScript 代码实现

下面是 JavaScript 中堆排序算法的代码实现，包括构建堆和堆化排序两个核心函数：```javascript
function heapify(arr, n, i) {
let largest = i; // Initialize largest as root
const left = 2 * i + 1;
const right = 2 * i + 2;
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]]; // Swap
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
function heapSort(arr) {
const n = ;
// Build heap (rearrange array)
for (let i = (n / 2 - 1); i >= 0; i--) {
heapify(arr, n, i);
}
// One by one extract an element from heap
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // Move current root to end
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}

// 示例用法
let arr = [12, 11, 13, 5, 6, 7];
heapSort(arr);
("Sorted array is: " + arr); // Output: Sorted array is: 5,6,7,11,12,13
```

这段代码清晰地展示了堆排序的两个主要步骤。`heapify` 函数负责维护最大堆的性质，而 `heapSort` 函数则协调整个排序过程。

四、性能分析

堆排序的时间复杂度为 O(n log n)。构建堆需要 O(n) 的时间，而堆化排序需要 O(n log n) 的时间。因此，总的时间复杂度为 O(n log n)。堆排序的空间复杂度为 O(1)，因为它是一种原地排序算法。与快速排序相比，堆排序的性能更稳定，不会出现最坏情况下的 O(n²) 时间复杂度。但是，在实际应用中，快速排序通常比堆排序更快，因为快速排序的常数因子更小。选择哪种排序算法取决于具体的应用场景和数据特征。

五、总结

堆排序是一种高效且稳定的排序算法，其时间复杂度为 O(n log n)，空间复杂度为 O(1)。本文详细介绍了堆排序的原理、代码实现以及性能分析。理解堆排序不仅有助于提升算法能力，也为选择合适的排序算法提供了重要的参考依据。虽然在某些情况下快速排序表现更好，但堆排序的稳定性和最坏情况下的性能保证，使其在特定应用场景中依然具有不可替代的价值。

2025-05-04

上一篇：JavaScript绘图：从入门到进阶，玩转Canvas和SVG

下一篇：HTML中嵌入JavaScript的多种方法及最佳实践