java - 快速排序实现错误java

Question

我在下面的快速排序实现中做错了什么:

public static void quicksort(int[] array, int start, int end) {
    while (start < end) {
        int pIndex = partition(array, start, end);
        quicksort(array, start, pIndex - 1);
        quicksort(array, pIndex + 1, end);
    }
}

public static int partition(int[] array, int start, int end) {
    int pivot = array[end];
    int pIndex = start;
    for (int i = start; i <= end - 1; i++) {
        if (array[i] <= pivot) {
            int tmp = array[pIndex];  // swap values
            array[pIndex] = array[i];
            array[i] = tmp;
            pIndex++;
        }
    }
    int tmpVal = array[pIndex];
    array[pIndex] = pivot;
    array[end] = tmpVal;
    return pIndex;
}

当针对数组 {7, 5, 3, 6, 8, 1, 2, 4} 的测试用例运行它时，它将数组重新排列为 {1, 2, 3, 4, 8, 5, 7 , 6} 它对数组的左侧进行排序，但随后进入似乎是 {1, 2} 数组的无限循环，并且永远不会离开该递归调用。我尝试添加一个基本情况，如果 array.length 小于 2，则返回；但这没有区别。

这是我的 code 的链接.

有人知道哪里出了问题吗？

Answer 1

你的循环

for (int i = 0; i <= end - 1; i++) {

分区内应该是

for (int i = start; i <= end - 1; i++) {

如果没有这个，您的 pIndex 可能会超出 start 到 end 的范围，并且您对快速排序的递归调用将具有相同的参数。

编辑

上面没有显示的你的ideone代码的另一个问题是

if (array.length < 2) { return; }

在 quicksort 中，您不会更改数组的长度，因此 array.length 将始终为 8。

第三个问题，导致无限循环的是

while (start < end) {

在 quicksort 中，您不会在此循环期间更改开始或结束的值，因此此循环永远不会退出。见https://ideone.com/wY23C6一个工作示例。