堆排序/Heap Sort ✓

堆排序

堆排序(Heap Sort)是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了。

步骤

1. 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
2. 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
3. 反复执行调整+交换步骤，直到整个序列有序。

//堆排序使用的创建顶堆
const createMaxHeap = (arr, len) => {
    const create = (arr, i, len) => {
        let maxIndex = i;
        let left = 2 * i;
        let right = 2 * i + 1;
        if (left < len && arr[maxIndex] < arr[left]) {
            maxIndex = left;
        }
        if (right < len && arr[maxIndex] < arr[right]) {
            maxIndex = right;
        }
        let temp = arr[maxIndex];
        arr[maxIndex] = arr[i];
        arr[i] = temp;
    }
    for (let i = Math.floor(len / 2); i >= 0; i--) {
        create(arr, i, len);
    }
}

/**
 * 堆排序
 * 循环创建最小堆，依次取出堆顶元素
 */
const heapSort = (arr) => {
    for (let i = arr.length - 1; i >= 0; i--) {
        createMaxHeap(arr, i + 1);
        let max = arr[0];
        arr[0] = arr[i];
        arr[i] = max;
    }
    return arr;
}

Try in StackBlitz