SOURCE

// 单独开辟两个存储空间left和right来存储每次递归比target小和大的序列
// 每次递归直接返回left、target、right拼接后的数组
// 浪费大量存储空间，写法简单

function quickSort(array) {
    if (array.length < 2) {
        return array;
    }
    // 对比的数字
    const target = array[0];
    console.log(target)
    // 小于对比的数字
    const left = [];
    // 大于对比的数字
    const right = [];
    for (let i = 1; i < array.length; i++) {
        // 小于的丢左边
        if (array[i] < target) {
            left.push(array[i]);
        } else {
            // 大于的丢右边
            right.push(array[i]);
        }
    }
    return quickSort(left).concat([target], quickSort(right));
}

console.log(quickSort([5, 3, 2, 8, 4, 6, 7, 9, 1]))

// c: 5 l: 3,2,4,1 r: 8,6,7,9 -> 1,2,3,4,5,6,7,8,9
// left
// c: 3 l: 2,1 r: 4 -> 1,2,3,4
// c: 2 l: 1 r: [] -> 1,2
// right
// c: 8 l: 6,7 r: 9 -> 6,7,8,9
// c: 6 l: [] r: 7 -> 6,7
// 6,7
//

function quickSort2(arr) {
    // 如果只有0、1个数字
    if (arr.length < 2) {
        return arr
    }
    // 设置第一个为中间数
    const target = arr[0]
    let left = []
    let right = []

    for (i = 1; i < arr.length; i++) {
        if (arr[i] < target) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }

    return quickSort2(left).concat([target], quickSort2(right))

}

console.log(quickSort2([88, 59, 26, 64, 35, 2, 10, 01]))