使用快速排序求数组最大三数乘积时输出undefined的问题排查

核心错误点 #

• 递归无返回值：greatestProduct里的递归调用执行后没有返回结果，上层函数拿不到基准条件返回的乘积值，最终输出undefined。
• 基准条件逻辑错误：当前end - start <= 0的基准条件触发时，数组未必完全排序完成，此时计算乘积会得到错误结果；且快速排序的终止条件应该是start >= end时停止递归，而非直接计算乘积。
• 职责混淆：greatestProduct同时承担排序和计算乘积的职责，逻辑混乱，应该拆分功能，先完成排序再计算乘积。
• 分区函数缩进问题：partition里的leftPointer += 1不在else块内，会导致交换元素后指针移动逻辑错误。

修复后的代码 #

// 快速排序函数
function quickSort(array, start, end) {
    if (start >= end) {
        return;
    }
    let pivot = partition(array, start, end);
    quickSort(array, start, pivot - 1);
    quickSort(array, pivot + 1, end);
}

// 分区函数
function partition(array, leftPointer, rightPointer) {
    const pivotIndex = rightPointer;
    const pivotValue = array[pivotIndex];
    rightPointer -= 1;
    while(true) {
        while(array[leftPointer] < pivotValue){
            leftPointer += 1;
        }
        while(array[rightPointer] > pivotValue){
            rightPointer -= 1;
        }
        if(leftPointer >= rightPointer){
            break;
        } else {
            [array[leftPointer], array[rightPointer]] = [array[rightPointer], array[leftPointer]];
            leftPointer += 1;
        }
    }
    [array[leftPointer], array[pivotIndex]] = [array[pivotIndex], array[leftPointer]];
    return leftPointer;
}

// 计算最大三数乘积
function greatestProduct(array) {
    quickSort(array, 0, array.length - 1);
    return array[array.length - 1] * array[array.length - 2] * array[array.length - 3];
}

let myArray = [2,4,1,6,3,5];
console.log(greatestProduct(myArray)); // 输出 120

修复说明 #

1. 拆分quickSort和greatestProduct函数，各自负责排序和乘积计算，逻辑更清晰。
2. 修正快速排序的终止条件：当start >= end时直接返回，停止递归。
3. 在greatestProduct中先完成数组排序，再取排序后最后三个元素（最大的三个数）计算乘积，确保结果正确。
4. 修复partition函数的缩进问题，保证指针移动逻辑在else块内执行。

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