编辑代码

// 快速排序
const quickSort = arr => {
    const len = arr.length
    if (len <= 1) return arr

    const mid = arr.splice(Math.floor(len / 2), 1)[0]
    const left = []
    const right = []

    for (let i = 0; i < len - 1; i++) {
        if (arr[i] < mid) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([mid], quickSort(right))
}
// console.log(quickSort([3, 1, 6, 8, 6, 4, 2, 6, 8, 6, 3]))

// 快速排序优化
const quickSort2 = (arr, left = 0, right = arr.length-1) => {
    if (arr.length <= 1) return arr
    const mid = partition(arr, left, right)
    // 因为返回的数值越过了mid 所以需要再减1
    if (left < mid-1) {
        quickSort2(arr, left, mid-1)
    }
    if (right > mid) {
        quickSort2(arr, mid, right)
    }
    return arr
}
// 调换左右位置
const partition = (arr, left, right) => {
    let i = left, j = right;
    const mid = arr[Math.floor((left + right) / 2)]
    while (i <= j) {
        while (arr[i] < mid) {
            i++
        }
        while (arr[j] > mid) {
            j--
        }
        if (i <= j) {
            [arr[i], arr[j]] = [arr[j], arr[i]]
            i++
            j--
        }
    }
    return i
}
console.log(quickSort2([3, 1, 6, 8, 6, 4, 2, 6, 8, 6, 3]))