快速排序实现中swap函数无法正常工作的原因是什么？

问题汇总 #

• swap函数传参错误：调用swap时第一个参数多包裹了一层数组，你写的swap([array[i]], array[j])会导致第一个入参是数组类型，和swap预期的单个值入参不符，返回的数组结构完全错误，无法完成交换。
• 右指针移动逻辑错误：内层while (array[j] > pivot)的循环体中你写了j++，右指针应该从右向左遍历寻找小于基准值的元素，需要改为j--，否则会直接导致数组越界或者死循环。
• 基准值下标计算错误：(l + r) / 2可能得到小数，无法作为数组下标使用，需要补充取整逻辑，例如用Math.floor((l + r) / 2)。
• 可选优化：JavaScript原生支持数组解构赋值交换变量，可以直接省略swap函数，写[array[i], array[j]] = [array[j], array[i]]即可完成交换，减少不必要的函数调用。

修正后完整代码 #

// 保留原swap写法的实现版本
function swap(a, b) {
    return [b,a];
}

function partition(array, l, r) {
    // 补全下标取整逻辑
    let pivot = array[Math.floor((l + r) / 2)];
    let i = l;
    let j = r;

    while (i <= j) {
        while (array[i] < pivot)
            i++;
        // 修正右指针移动方向为递减
        while (array[j] > pivot)
            j--;
        if(i >= j)
            return j;
        // 修正swap传参，去掉多余的数组包裹
        [array[i], array[j]] = swap(array[i], array[j]);
        // 交换后移动指针，避免重复比较相同元素导致死循环
        i++;
        j--;
    }
}

function qsort(arr, left, right) {
    if (left < right) {
        let q = partition(arr, left, right)
        qsort(arr, left, q);
        qsort(arr, q + 1, right);
    }
}

// 测试用例
const testArr = [3,1,4,1,5,9,2,6]
qsort(testArr, 0, testArr.length - 1)
console.log(testArr) // 输出 [1,1,2,3,4,5,6,9]

内容的提问来源于stack exchange，提问作者Rume One