算法学习：前端实现快排，堆排，优先级队列（JS）
快排
快排的实现基于分层（partition）和分治，先来了解什么是分层。
荷兰国旗问题
荷兰国旗是由红白蓝3种颜色的条纹拼接而成，如下图所示：
给定一个整数数组，给定一个值K，这个值在原数组中一定存在，要求把数组中小于K的元素放到数组的左边，大于K的元素放到数组的右边，等于K的元素放到数组的中间，最终返回一个整数数组，其中只有两个值，分别是等于K的数组部分的左右两个下标值。
例如，给定数组：[2, 3, 1, 9, 7, 6, 1, 4, 5]，给定一个值4，那么经过处理原数组可能得一种情况是：[2, 3, 1, 1, 4, 9, 7, 6, 5]，需要注意的是，小于4的部分不需要有序，大于4的部分也不需要有序，返回等于4部分的左右两个下标，即[4, 4]
求解过程：
left 用于记录小于 4 的区域的右下标，初始为-1，代表不存在
right 用于记录大于 4 区域的左下标，初始为9，代表不存在
index 用于正在遍历的元素的下标，初始值为0
从 arr[index] 即 arr[0] 开始遍历数组
如果 arr[index] > 4, 交换 arr[++left] 和 arr[index++] 的值
如果 arr[index] < 4, 交换 arr[--right] 和 arr[index] 的值
如果 arr[index] = 4, 不交换，L++，直接遍历下一个值
当 index >= right，退出循环。
代码实现:
function swap (arr, index1, index2) { if (index1 === index2) { return } let temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp } function partition(arr, criterion) { let index = 0 let left = -1 let right = arr.length while (index < right) { if (arr[index] < criterion) { swap(arr, ++left, index++) } else if (arr[index] > criterion) { swap(arr, --right, index) } else { index++ } } return [left + 1, right - 1] } partition([2, 3, 1, 9, 7, 6, 1, 4, 5], 4) 复制代码快排的实现
荷兰问题的求解就是快排中的partition过程，每次partition过程都会确定一个值（criterion）的排序结果，partition返回一个数组，即为基准元素（已排好序）的下标，递归执行左侧和右侧，即完成快排。 快排能作为O(logN * N)的算法，是因为基准元素需要做到随机选取，不受数据最好情况和最坏情况的影响，所以可以做到算法的长期期望是O(logN * N)。
快排代码如下：
function swap (arr, index1, index2) { if (index1 === index2) { return } let temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp } function partition(arr, left, right) { // 3 数组的最右项即为基准 const criterion = arr[right] let index = left while (index <= right) { if (arr[index] < criterion) { swap(arr, left++, index++) } else if (arr[index] > criterion) { swap(arr, right--, index) } else { index++ } } return [left, right] } function process(arr, left, right) { if (left >= right) { return } // 1 在左右范围内任意选取一个基准值进行分层 const random = (Math.random() * (right - left + 1) | 0) + left // 2 将选取的基准值和最右边的项交换位置 swap(arr, random, right) const [leftPart, rightPart] = partition(arr, left, right) process(arr, left, leftPart - 1) process(arr, rightPart + 1, right) } function quickSort (arr) { process(arr, 0, arr.length - 1) } 复制代码快排的时间复杂度是O(logN * N)，空间复杂度是O(logN)（递归栈的层数决定，平均下来是O(logN)）
堆排序
首先，了解堆结构。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
这种数据结构（完全二叉树），正好可以用数组来存储。父子节点的关系是：
leftChild = parentNode * 2 + 1 (左子节点的索引：父节点索引 * 2 + 1)
rightChild = parentNode * 2 + 2 (右子节点的索引：父节点索引 * 2 + 1)
上图大顶堆，可由数组表示，如下：
堆的常见两种操作：
heapInsert 向堆中插入数据
用数组表示堆，向数组中的某个位置插入数据，即为向堆中插入数据，那么每次插入数据后，需要调整堆，保持当前堆是大顶堆or小顶堆。
调整的过程，根据需要调整的元素索引，寻找他的父节点，父子节点大小比值，如果不符合大顶堆or小顶堆（每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆）就交换位置，并继续往上调整。代码如下（大顶堆）：
function swap (arr, index1, index2) { if (index1 === index2) { return } let temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp } // 向上调整 function heapInsert(arr，index) { let child = index let parent = (index / 2) | 0 // 子节点的值 > 父节点的值，不符合小顶堆的定义，交换位置 while (arr[child] > arr[parent]) { swap(arr, child, parent) child = parent parent = (child / 2) | 0 } } 复制代码heapify 向堆顶取出数据，向下调整堆结构
调整的过程，根据需要调整的元素索引，向下寻找他的子节点，父节点和（左右子节点的较大者（小顶堆判断较小者））大小比值，如果不符合大顶堆or小顶堆就交换位置，并继续往下调整。代码如下（大顶堆）：
// 向下调整 function heapify(arr，index) { let parent = index let heapSize = arr.length let leftChild = parent * 2 + 1 while (leftChild < heapSize) { // 求左右子节点的较大者，注意不能越界 let largest = leftChild + 1 < heapSize && arr[leftChild + 1] > arr[leftChild] ? leftChild + 1 : leftChild if (arr[largest] > arr[parent]) { swap(arr, largest, parent) } parent = largest leftChild = parent * 2 + 1 } } 复制代码有了heapify和heapInsert两类操作，现在可以对数组进行排序了，思路：
从数组的第0项遍历从数组的最后一项，增加堆的长度，并调整成为堆结构，heapInsert
不断的取出堆顶元素，放在从数组的最后一项，同时减小堆长度，并调整成新的堆, heapify
代码如下：
function swap (arr, index1, index2) { if (index1 === index2) { return } let temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp } // 大顶堆 function heapSort(arr) { let heapSize = 0 // 向下调整 function heapify(index) { let parent = index let leftChild = parent * 2 + 1 while (leftChild < heapSize) { let largest = leftChild + 1 < heapSize && arr[leftChild + 1] > arr[leftChild] ? leftChild + 1 : leftChild if (arr[largest] > arr[parent]) { swap(arr, largest, parent) } parent = largest leftChild = parent * 2 + 1 } } // 向上调整 function heapInsert(index) { let child = index let parent = (index / 2) | 0 while (arr[child] > arr[parent]) { swap(arr, child, parent) child = parent parent = (child / 2) | 0 } } let index = 0 // 从数组的第0项 - 从数组的最后一项，形成一个堆结构 for (; index < arr.length; index++) { heapInsert(index) // 此处也可以用heapify调整，效率更好 heapSize++ } index = 0 // 不断的取出堆顶元素，放在从数组的最后一项，减小堆长度，并调整成新的堆 for (; index < arr.length; index++) { swap(arr, 0, heapSize - 1) heapSize-- heapify(0) } } 复制代码堆排的时间复杂度是O(logN * N)，空间复杂度是O(1)
优先级队列
根据堆的效果，可以用JS实现JAVA和其他语言中的最大/最小优先级队列，代码如下：
class PriorityQueue { constructor(compare = (a, b) => a - b) { this.compare = compare; this.queue = []; } // 新增数据 offer(value) { this.queue.push(value) this._heapInsert() } // 弹出堆顶数据 poll() { if (!this.queue.length) { return null } const top = this.queue.shift() this._heapify() return top } _swap (arr, index1, index2) { if (index1 === index2) { return } let temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp } _heapify() { let parent = 0 let left = parent * 2 + 1 while (left < this.queue.length) { let operator = (left + 1 < this.queue.length) && this.compare(this.queue[left + 1], this.queue[left]) > 0 ? left + 1 : left if (this.compare(this.queue[operator], this.queue[parent]) > 0) { this._swap(this.queue, operator, parent) } parent = operator left = parent * 2 + 1 } } _heapInsert() { let child = this.queue.length - 1 let parent = (child / 2) | 0 while (this.compare(this.queue[child], this.queue[parent]) > 0) { this._swap(this.queue, child, parent) child = parent parent = (child / 2) | 0 } } }
作者：DY
链接：https://juejin.cn/post/7031458614015426568