JS实现O(logN*N)的排序：快排，堆排

另外一种O(logN*N)的排序：归并排序，请看juejin.cn/post/703107…

快排

快排的实现基于分层（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两类操作，现在可以对数组进行排序了，思路：

1. 从数组的第0项遍历从数组的最后一项，增加堆的长度，并调整成为堆结构，heapInsert
2. 不断的取出堆顶元素，放在从数组的最后一项，同时减小堆长度，并调整成新的堆, 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
        }
    }
}