堆排序在JavaScript中的实现

堆排序是一种基于比较的高效排序算法，它利用了二叉堆数据结构。堆排序具有稳定的性能表现，在平均和最坏情况下的时间复杂度均为 O(n log n)。本文将详细介绍堆排序的概念、原理，并提供一个简单的JavaScript实现。

堆排序原理

堆排序基于完全二叉树结构的性质，可以分为构建最大堆和维护堆两大步骤：

1. 构建最大堆：从数组中构建一个最大堆，确保每个父节点的值都大于或等于其子节点。
2. 维护堆：将堆顶元素（即最大值）与最后一个元素交换，然后将堆的大小减一，重新调整剩余元素以保持最大堆的性质。重复此过程直到堆的大小为1。

JavaScript 实现

以下是一个使用JavaScript实现堆排序的例子：

function heapify(arr, n, i) {
    let largest = i; // 初始化最大值索引为当前索引
    const left = 2 * i + 1; // 左子节点
    const right = 2 * i + 2; // 右子节点

    // 检查左子节点是否存在且大于当前最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 检查右子节点是否存在且大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是当前索引
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]]; // 交换值
        // 递归地对受影响的子堆进行调整
        heapify(arr, n, largest);
    }
}

function heapSort(arr) {
    const n = arr.length;

    // 构建最大堆
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 从堆顶逐个取出元素
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]]; // 将当前最大值移到末尾
        heapify(arr, i, 0); // 调整剩余部分的最大堆
    }

    return arr;
}

// 示例使用
const exampleArray = [12, 11, 13, 5, 6, 7];
const sortedArray = heapSort(exampleArray);
console.log(sortedArray); // 输出: [5, 6, 7, 11, 12, 13]

解释

1. heapify 函数：这个函数负责维护堆的性质。它首先确定当前节点是否是最大值，如果不是，则交换该节点与最大值，并递归调用自身以调整受影响的子堆。

2. heapSort 函数：这个函数首先构建一个最大堆，然后通过交换堆顶元素（最大值）和末尾元素，逐步构建有序数组。每次交换后，调用 heapify 来确保剩余部分仍然保持最大堆的性质。

通过这种方式，我们可以高效地对数组进行排序，适用于各种规模的数据集。堆排序尤其适合处理大数据量的情况，因为它的时间复杂度始终为 O(n log n)，在所有排序算法中属于较快的一种。