SOURCE

/**
 * 快速排序(原地排序，取最右侧元素作为基准)
 * @params {number[]} arr 待排序数组
 * @params {number} left 当前处理区间左边界下标，默认0
 * @params {number} right 当前处理区间右边界下标，默认数组最后一位下标
 * @returns {number[]} 排序后的原数组
 */
function quickSort(arr, left = 0, right = arr.length - 1) {
    // 递归终止条件：区间只有0个或者1个元素，无需排序
    if (left >= right) return arr
    // 分区：返回基准元素最终所在下标
    const pivot = partition(arr, left, right)
    // 递归处理基准左侧区间
    quickSort(arr, left, pivot - 1)
    // 递归处理基准右侧区间
    quickSort(arr, pivot + 1, right)
    return arr
}
/**
 * 分区函数：把区间内小于基准的值放在左边，大于等于的放右边
 */
function partition(arr, left, right) {
    // 选取区间最右侧的值作为基准值
    const baseVal = arr[right]
    // 下一个存在【小于基准值】元素的位置
    let index = left
    // 遍历区间，逐个和基准值比较
    for (let i = left; i < right; i++) {
        // 当前元素小于基准值，交换到index位置，index右移
        if (arr[i] < baseVal) {
            [arr[index], arr[i]] = [arr[i], arr[index]]
            index++
        }
    }
    // 循环结束后，index左边全部小于基准值
    // 将基准元素放到index位置，此时index就是基准的最终位置
    [arr[index], arr[right]] = [arr[right], arr[index]]
    return index
}

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