sorting - 快速排序逻辑

Question

我正在尝试在 java 中实现快速排序，但我有一个疑问。所以这是我的快速排序代码：

package com.sorting;

public class QuickSort implements Sort {

@Override
public int [] sort(int[] arr) {
    return quickSort(arr, 0, arr.length - 1);
}

private int [] quickSort(int[] numbers, int low, int high) {

    if (low < high) {
        int q = partitionTheArrayAroundPivot(numbers, low, high);

        if (low < q)
            quickSort(numbers, low, q);

        if ((q+1) < high)
            quickSort(numbers, q + 1, high);
    }

    return numbers;
}

private int partitionTheArrayAroundPivot(int[] numbers, int low, int high) {

    int pivot = selectPivot(numbers, low, high);
    int i = low;
    int j = high;

    while (true) {

            while (numbers[i] < pivot) {
            i++;
        }

            while (numbers[j] > pivot) {
            j--;
        }

        if ( i <= j) {
            swap(numbers, i, j);
            i++;
            j--;
        } else {
            return j;
        }

    }

}

private int selectPivot(int[] numbers, int low, int high) {
    return numbers[high];
}

private void swap(int[] numbers, int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

}

疑问 1：我们不断增加索引 i 直到达到 >= pivot 的数字

while (numbers[i] < pivot)
    i++;

同样，我们不断减少索引j，直到我们达到 <= pivot 的数字

while (numbers[j] > pivot)
    j--;

因此，这意味着如果两个索引都在两个不同的位置（例如 1,0,1）在两个不同的位置枢轴，则两个索引也将退出循环，如果枢轴为 1，则 i 将为 0，j 将为 2。下面的条件将满足 if (i <= j) { .... } 但在这种情况下，它将无法对上述数组 (1,0,1) 进行排序，因为交换后我们正在增加 i 并减少 j 所以值变为 i = j = 1。之后，我将命中第三个元素，即 1，并再次以 i = 2 和 j = 0 的值退出循环，我们将无法对数组进行排序。

那么问题出在哪里？我错过了什么吗？

Answer 1

我会稍微重写代码，以便 selectPivot 返回索引：

private int selectPivotIndex(int[] numbers, int low, int high) {
    return high;
}

然后分区函数可以将枢轴移到一边，并根据枢轴值对剩余的项目进行排序。一个循环就可以了，在这个实现中，重复的枢轴将在右侧结束：

private int partitionTheArrayAroundPivot(int[] numbers, int low, int high) {

    int pivotIndex = selectPivotIndex(numbers, low, high);

    swap(numbers, pivotIndex, high); // Not needed if selectPivotIndex always returns high
    int newPivotIndex = low;
    for(int i = low; i < high; i++)
    {
        if(numbers[i] < numbers[pivotIndex])
        {
            swap(numbers, i, newPivotIndex);
            newPivotIndex++;
        }
    }
    swap(numbers, newPivotIndex, pivotIndex);

    return newPivotIndex;
}

最后，需要在quickSort方法中做一个小的调整，这样我们就不会陷入一个永恒的循环：

if (low < q)
      quickSort(numbers, low, q - 1);

恕我直言，这种方法更易于理解和调试，希望它对您有用。

Answer 2

使用
while (numbers[i] <= pivot)and while (numbers[j] >= pivot)你的代码就可以工作了