kuisu1

/* 合并左子数组和右子数组 */
/* 元素交换 */
swap(nums, i, j) {
    let tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* 哨兵划分 */
partition(nums, left, right) {
    // 以 nums[left] 为基准数
    let i = left,
        j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j -= 1; // 从右向左找首个小于基准数的元素
        }
        while (i < j && nums[i] <= nums[left]) {
            i += 1; // 从左向右找首个大于基准数的元素
        }
        // 元素交换
        this.swap(nums, i, j); // 交换这两个元素
    }
    this.swap(nums, i, left); // 将基准数交换至两子数组的分界线
    return i; // 返回基准数的索引
}

/* 快速排序 */
quickSort(nums, left, right) {
    // 子数组长度为 1 时终止递归
    if (left >= right) return;
    // 哨兵划分
    const pivot = this.partition(nums, left, right);
    // 递归左子数组、右子数组
    this.quickSort(nums, left, pivot - 1);
    this.quickSort(nums, pivot + 1, right);
}

let arr = [64, 34, 25, 12, 22, 11, 90]
console.log('排序前的数组: ', arr)
let sortedArr = quickSort(arr,0, arr.length - 1)
console.log('排序后的数组: ', sortedArr)