关于前端:排序算法堆排序JavaScript及Java实现

残缺代码

JavaScript 实现
https://github.com/Jiacheng78…

Java 实现
https://github.com/Jiacheng78…

堆的概念

个别堆排序里的堆指的是二叉堆，是一种齐全二叉树。齐全二叉树有一个性质是，除了最底层，每一层都是满的，这使得堆能够利用数组来示意，每个结点对应数组中的一个元素。

二叉堆有两种： 最大堆和最小堆 。最大堆所有父节点的值大于子节点的值，最小堆所有父节点的值小于子节点的值。

显然，最大堆堆顶元素必然是堆中最大的元素，最小堆堆顶元素是堆中最小的元素

堆排序实现

上面应用 JavaScript 代码介绍堆排序实现。

首先须要初始化一个二叉堆，后面介绍了二叉堆实际上就是一个数组，因而初始化非常简单：

constructor(arr) {this.data = [...arr];
    this.size = this.data.length;
}

在初始化的时候，如果某一结点不合乎二叉堆的性质，须要将该节点与两个子节点进行替换。具体流程是，以后节点与两个子节点进行比照，如果不合乎二叉堆性质，取三个外面的最大值并进行替换，替换后的子节点持续递归进行后续子树的替换：

maxHeapify(i) {
    let max = i; // 保留最大的节点下标

    if (i >= this.size) return;

    const left = i * 2 + 1; // 左节点下标
    const right = i * 2 + 2; // 右节点下标

    if ((left < this.size) && (this.data[left] > this.data[max])) {max = left;}

    if ((right < this.size) && (this.data[right] > this.data[max])) {max = right;}

    if (max === i) return; // 如果最大节点是其自身，不进行替换

    [this.data[i], this.data[max]] = [this.data[max], this.data[i]];

    return this.maxHeapify(max);
}

要害代码：
const left = i * 2 + 1; // 获取左节点
const right = i * 2 + 2; // 获取右节点

下面的 maxHeapify 函数只能对某一结点进行对调，无奈对整个数组进行重构。结构一个最大堆须要获取到所有的分支节点（不含叶子节点），而后对每个分支节点顺次进行递归重构：

rebuildHeap() {
    // 获取分支节点
    const L = Math.floor(this.size / 2);
    for(let i = L - 1; i >= 0; i--){
        // 每个 i 都代表一个分支节点的下标
        this.maxHeapify(i);
    }
}

要害代码：
const L = Math.floor(this.size / 2); // 获取分支节点

留神上一步实现后数组还并没有实现排序，只是根本有序，上面进行排序操作。从最初一个元素开始，和堆顶元素替换，而后 size- 1 将最初一个元素拆散出堆，调用 maxHeapify 维持最大堆性质。因为堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被拆散出堆，反复 n - 1 次之后，数组排列结束：

sort() {for(let i = this.size - 1; i > 0; i--){[this.data[0], this.data[i]] = [this.data[i], this.data[0]];
        this.size--; // 将替换后的元素拆散出堆
        this.maxHeapify(0);
    }
    this.size = this.data.length; // 排序实现后从新获取 size
}

如果是从小到大排序，用最大堆；从大到小排序，用最小堆

工夫复杂度与稳定性

一道面试题