快速排序实现错误 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，则 return；但这没有区别。

这是我 code 的 link。

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

Answer 1

你的循环

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

在partition内应该是

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。

Answer 2

while (start < end) {
    int pIndex = partition(array, start, end);
    quicksort(array, start, pIndex - 1);
    quicksort(array, pIndex + 1, end);
}

应该是

if (start < end) {
    int pIndex = partition(array, start, end);
    quicksort(array, start, pIndex - 1);
    quicksort(array, pIndex + 1, end);
}

快速排序实现错误 java

quicksort implementation bug java

java

recursion

quicksort

编辑