SOURCE

// 思路
// 类似1~100累加的递归思路
// 将每层递归传入的数组切一半 小的放左边 大的放右边
// 直到递归传入的数组元素个数小于2 再一层一层向上返回
// 每层递归都将返回的数组降维 合并到当前层的数组
// 最后得到排序结果

function fn(list) {
    // 递归出口
    if (list.length < 2) {
        // 小于等于1 直接返回 因为已经是有序的
        return list
    }
    let mid = Math.floor(list.length / 2) // 中间位置
    let left = [] // 左数组
    let right = [] // 右数组
    for (let val of list) {
        // 注意 遍历时会取到中间值 必须要跳过 否则会死循环
        // 因为每次把中间值去掉 递归下去的数组才能越来越小
        if (val === list[mid]) {
            continue
        }
        if (val <= list[mid]) {
            left.push(val)
        } else {
            right.push(val)
        }
    }
    // 递归左右数组 将其结果合并成新数组
    return [...fn(left), list[mid], ...fn(right)]
}

// 验证
let list = [3, 6, 8, 10, 1, 2, 1]
console.log('快速排序：' + fn(list)) // [1,2,3,6,8,10]