编辑代码

/* 元素交换 */
function swap(arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
/**
 * 找中值
 * 保证  arr[min] <= arr[mid] <= arr[max]。
 * 合理的找出中值，确定pivot是选中间值 or 第一个位置 or 最后一个位置 ，可减少后续的对比次数
 */
function findPivot(arr, start, end) {
    const len = end - start
    let mid = start + (len >> 1) //0 -> 7 4
    let min = start
    let max = end - 1

    if (arr[min] > arr[mid]) {
        let temp = min
        min = mid;
        mid = temp
    }
    if (arr[mid] > arr[max]) {
        let temp = mid
        mid = max
        max = temp
    }

    if (arr[min] > arr[mid]) {
        let temp = min
        min = mid
        mid = temp
    }
    return mid
}


function partition(arr, left, right, pivotPos) {
    // 以 nums[left] 作为基准数
    let i = left,
        j = right;

    let mid = findPivot(
        arr,
        left,
        right
    );
    // 将中位数交换至数组最左端
    swap(arr, left, mid);
    // 以 nums[left] 作为基准数
    while (i < j) {
        while (i < j && arr[j] >= arr[left]) {
            j -= 1; // 从右向左找首个小于基准数的元素
        }
        while (i < j && arr[i] <= arr[left]) {
            i += 1; // 从左向右找首个大于基准数的元素
        }

        swap(arr, i, j); // 交换这两个元素
    }
    swap(arr, i, left); // 将基准数交换至两子数组的分界线,也就是最终空的那个位置
    return i; // 返回基准数的索引
}



// left,right 为索引
function quickSort(arr, left, right) {
    // 子数组长度为 1 时终止递归
    if (left >= right) return;

    const pivot = partition(arr, left, right);
    // 递归左子数组、右子数组
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
    return arr
}



const arr = [9, 8, 7, 6, 5, 4, 2, 1]
const arr2 = [9, 8, 5, 4, 2, 1, 7, 6]
const arr3 = [2, 1, 9, 8, 5, 4, 7, 6]
console.log(quickSort(arr, 0, arr.length - 1))
console.log(quickSort(arr2, 0, arr2.length - 1))
console.log(quickSort(arr3, 0, arr3.length - 1))