编辑代码

// 5、快速排序
function quickSort(arr, left = 0, right = arr.length - 1) {
    // 定义递归边界，若子数组只有一个元素，则没有排序必要
    if (arr.length > 1) {
        // 计算当前数组的基准值
        const nextPivot = partition(arr, left, right)
        // 如果左边子数组的长度不小于1，则递归快排这个子数组
        if (left < nextPivot - 1) {
            quickSort(arr, left, nextPivot - 1)
        }
        // 如果右边子数组的长度不小于1，则递归快排这个子数组
        if (nextPivot < right) {
            quickSort(arr, nextPivot, right)
        }
    }
    return arr
}

// 寻找基准值的过程
function partition(arr, left, right) {
    // 基准值默认值
    // const pivot = arr[left];
    const pivot = arr[Math.floor(left + (right - left) / 2)]
    // const pivot = getPivot(arr, left, right);
    // 当左右指针不越界时，循环执行以下逻辑
    while (left <= right) {
        // 左指针所指元素若不大于基准值，则右移左指针
        while (arr[left] < pivot) {
            left++
        }
        // 右指针所指元素若不小于基准值，则左移右指针
        while (arr[right] > pivot) {
            right--
        }
        // 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序
        if (left <= right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            left++
            right--
        }
    }
    // 返回左指针索引作为下一个基准值的索引
    return left;
}