试图编写快速排序算法而不添加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，这是因为它是一个可能需要交换的有效值(这与键/initialIndex值不同，后者是支点/绑定，处理方式不同)。

您可以将其更改为：

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

但是现在您将在数组通过finalIndex后得到一个超出范围的错误，因此您需要将其更改为：

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

因此，在尝试访问数组之前，它将首先检查数组限制。这应该能解决你的问题。

Answer 2

我找到的最简单的快速排序是：

function quicksort(arr)
{
    if (arr.length == 0)
        return [];
 
    var left = []
    var right = []
    var pivot = arr[0];
 
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
           left.push(arr[i]);
        } else {
           right.push(arr[i]);
        }
    }
 
    return quicksort(left).concat(pivot, quicksort(right));
}

以及2D数组的版本：

function quicksort_2D(options)
{
    /*
        options:
            arr     - arr to sort
            sortcol     - column position to sort on
            sorttype    - 
    */

    if (options.arr.length == 0)
        return [];
 
    var left = []
    var right = []
    var pivot = options.arr[0][options.sortcol];
 
    for (var i = 1; i < options.arr.length; i++) {
        if (options.arr[i][options.sortcol] < pivot) {
            left.push(options.arr[i]);
        } else {
            right.push(options.arr[i]);
        }
    }
    var pivotarr=[options.arr[0]]
    
    var retval = quicksort_2D({arr: left, sortcol: options.sortcol, sorttype: options.sorttype}).concat(pivotarr, quicksort_2D({arr: right, sortcol: options.sortcol, sorttype: options.sorttype}));
    return retval
}