经典算法-快排

快速排序quickSort

基本思想是，每一次选取一个基数，将原数组分割成三部分：基数、比基数小的新数组，比基数大的新数组。
之后递归执行，递归结束条件是传入的数组长度<=1。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr
    }
    let left = [], right = [], base = arr[0]
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < base) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([base], quickSort(right))
}