一直学，一直忘。希望这此能记牢。。

快速排序

递归版

分两个函数。

一个函数用来进行分区。

当递归到区间只有一个元素时，就可以视作排序完成而返回了。此时 p 两边的数组区间就排好序了。

另一个函数被递归调用，以对分区进行排序。

分区函数中，哨兵元素可以随机取 [l,r] 内的值。取区间最右的值比较方便。
可以理解为分为四个区间：

上图中，[left, i) 为小于哨兵的元素，图中为蓝色区间。[i,j} 为大于哨兵的元素，红色区间。[j,r) 为待比较元素，灰色区间。哨兵自己构成一个区间。

• 当前比较的元素小于哨兵时，交换当前比较的元素与 i 指向的元素，并且 i，j，都加 1。
• 当前比较的元素大于哨兵时，只需 j 加 1 即可。

JavaScript 完整代码：

function quickSort(arr, l, r) {
    if (r <= l) {
        return
    }
    let q = partition(arr, l, r);
    console.log(q);
    quickSort(arr, l, q - 1);
    quickSort(arr, q + 1, r);
}

function partition(arr, l, r) {
    let p = r;  // 可以随机选取 [l,r] 内的值, 这里选取最右作为哨兵索引
    // 将哨兵放到最右边, 便于排序.
    // 由于这里选取的是 r, 所以不用交换了
    // [arr[p], arr[r]] = [arr[r], arr[p]];
    let i = l;
    for (let j = l; j <= r - 1;) {
        if (arr[j] <= arr[r]) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i += 1;
        } 
        j += 1;
    }
    // 交换哨兵和比哨兵大的元素, 此时哨兵的位置就是最终位置了
    [arr[i], arr[r]] = [arr[r], arr[i]];
    return i;
}

递归版的参考视频，图片来源：
五点七边