快速排序

"快速排序"的思想很简单，整个排序过程只需要三步：

1. 在数据集之中，选择一个元素作为"基准"（pivot）。
2. 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

举例来说，现在有一个数据集{85, 24, 63, 45, 17, 31, 96, 50}，怎么对其排序呢？

第一步，选择中间的元素45作为"基准"。（基准值可以任意选择，但是选择中间的值比较容易理解。）

第二步，按照顺序，将每个元素与"基准"进行比较，形成两个子集，一个"小于45"，另一个"大于等于45"。

第三步，对两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

代码

/* 
快速排序
（1）在数据集之中，选择一个元素作为"基准"（pivot）。
（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
*/

function quickSort(arr) {
    // 出口
    if (arr.length <= 1) { // 最后数组可能是空，可能只剩一个值
        return arr
    }

    // 找基准 pivot（假如以数组中间的那个值为基准）
    let pivotIndex = Math.floor(arr.length / 2)
    let pivot = arr.splice(pivotIndex, 1)[0] // 把基准取出来，并改变原数组（splice会把原来的数组改变）

    let left = [] // 比基准小的值 放左边
    let right = [] // 比基准大的值 放右边

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) { // 比基准小的放左边
            left.push(arr[i])
        } else { // 比基准大的或者相等的放右边
            right.push(arr[i])
        }
    }

    // 递归，一直透到底
    // 左边的 + 基准 + 右边的

    return quickSort(left).concat(pivot, quickSort(right))
}


let arr = [10, 7, 9, 11, 22, 33, 4, 2]

let newArr = quickSort(arr)

console.log(newArr); // 
/* 
[
   2,  4,  7,  9,
  10, 11, 22, 33 
]
*/

参考

https://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html