堆排序算法

学号：20021211189       姓名：赵治伟

【嵌牛导读】堆排序（Heapsort）是利用二叉堆的概念来排序的选择排序算法，分为两种：

升序排序：利用最大堆进行排序

降序排序：利用最小堆进行排序

【嵌牛鼻子】堆排序算法

【嵌牛正文】

1.算法原理

给定一个最大堆如下图所示，以该最大堆进行演示堆排序

首先，删除堆顶元素10（即最大的元素），并将最后的元素3补充到堆顶，删除的元素10，放置于原来最后的元素3的位置

根据二叉堆的自我调整，第二大的元素9会成为二叉堆新的堆顶

删除元素9，元素8成为最大堆堆顶

删除元素8，元素7成为最大堆堆顶

依次删除最大元素，直至所有元素全部删除

此时，被删除的元素组成了一个从小到大排序的序列

2.算法实现

// 下沉调整

// 最大堆

function downAdjust(arr, parentIndex, length) {

    // 缓存父节点的值，用于最后进行赋值，而不需要每一步进行交换

    let temp = arr[parentIndex];

    // 孩子节点下标，暂时定为左孩子节点下标

    let childIndex = 2 * parentIndex + 1;

    while (childIndex < length) {

        // 当存在右孩子节点，且右孩子节点的值小于左孩子节点的值，childIndex记录为右孩子节点的下标

        // childIndex实际记录的是最小的孩子节点的下标

        if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {

            childIndex++;

        }

        // 如果父节点的值比孩子节点的值都小，则调整结束

        if (temp >= arr[childIndex]) {

            break;

        }

        // 将最小的孩子节点的值赋值给父节点

        arr[parentIndex] = arr[childIndex];

        parentIndex = childIndex;

        childIndex = 2 * parentIndex + 1;

    }

    arr[parentIndex] = temp;

}

// 堆排序

function sort(arr) {

    // 把无序数组构建成二叉堆

    for (let i = parseInt(arr.length / 2) - 1; i >= 0; i--) {

        downAdjust(arr, i, arr.length);

    }

    console.log(arr);

    // 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶

    for (let i = arr.length - 1; i > 0; i--) {

        // 最后一个元素与第一个元素交换

        [arr[0], arr[i]] = [arr[i], arr[0]];

        downAdjust(arr, 0, i);

    }

}

let arr = [10, 9, 8, 5, 6, 7, 1, 4, 2, 3];

sort(arr);

console.log(arr);

堆排序算法特点

1.时间复杂度

下沉调整的时间复杂度等同于堆的高度O(logn)，构建二叉堆执行下沉调整次数是n/2，循环删除进行下沉调整次数是n-1，时间复杂度约为O(nlogn)

2.空间复杂度

堆排序算法排序过程中需要一个临时变量进行两两交换，所需要的额外空间为1，因此空间复杂度为O(1)

3.稳定性

堆排序算法在排序过程中，相同元素的前后顺序有可能发生改变，所以堆排序是一种不稳定排序算法