javascript - 试图在不制作 2 个新列表和附加的情况下编写快速排序算法，无法找出问题所在

Question

刚开始编码并尝试了几个小时来弄清楚为什么我得不到终端输出。有什么猜测吗？

const unsortedArray = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];
let initialIndex, finalIndex, i, j;

function quickSort(initialIndex, finalIndex, unsortedArray) {
    if(initialIndex >= finalIndex) {
        return unsortedArray;
    }

    let key = initialIndex;
    let i = initialIndex + 1;
    let j = finalIndex;

    while(i <= j) {

        while (unsortedArray[i]<=unsortedArray[key] && i<finalIndex) {
            i++;
        }
        
        while (unsortedArray[j]>=unsortedArray[key] && j>initialIndex) {
            j--;
        }
    
        if(i > j) {
            let temp = unsortedArray[initialIndex];
            unsortedArray[initialIndex] = unsortedArray[j];
            unsortedArray[j] = unsortedArray[initialIndex];
        } else {
            let temp = unsortedArray[i];
            unsortedArray[i] = unsortedArray[j];
            unsortedArray[j] = temp;
        }
        
    }
    quickSort(initialIndex,j-1,unsortedArray);
    quickSort(j+1,finalIndex,unsortedArray);
    return unsortedArray
}

function showSortedArray (unsortedArray) {
    quickSort(0, unsortedArray.length-1, unsortedArray);
    console.log(unsortedArray);
}

showSortedArray(unsortedArray);

我已经找到了其他方法(创建两个新数组并向左和向右追加)，但我想在这种方法中取得成功。

Answer 1

只要 i 和 j 都等于 finalIndex 值，您的函数就会进入无限循环。

问题是这里的这一行:

    while (unsortedArray[i]<=unsortedArray[key] && i<finalIndex) {
        i++;
    }

因为你有 i<finalIndex ，我永远不会到达 finalIndex，它应该是因为它是一个可能需要交换的有效值(这与 key/initialIndex 值形成对比，后者是枢轴/绑定(bind)并且处理方式不同).

您可以将其更改为:

while (unsortedArray[i]<=unsortedArray[key] && i<=finalIndex) {

但是现在你在通过finalIndex之后会得到一个数组越界的错误，所以你需要改成这样:

while (i<=finalIndex && unsortedArray[i]<=unsortedArray[key]) {

所以现在它将在尝试访问数组之前首先检查数组限制。这应该可以解决您的问题。