java - 快速排序未完全排序提供的数组

Question

我的快速排序似乎在对数组进行完全排序之前就停止了，而且我对代码视而不见。

我根据Java软件结构 - 设计和使用数据结构(第三版)中的相关章节编写了算法

快速排序:

private static <T extends Comparable<T>> void quickSort(T[] array,int min, int max){

    int pIndex;

    if (max-min > 0) {

        pIndex = partition(array, min, max);

        quickSort(array, min, pIndex-1);

        quickSort(array, pIndex+1, max);

    }
}

分区:

private static <T extends Comparable<T>> int partition(T[] array, int min, int max) {

    int left, right;
    T pivot, temp;
    int middle = (min+max)/2;

    left  = min;
    right = max;
    pivot = array[middle];

    while (left < right) {

        while (array[left].compareTo(pivot) <= 0 && left < right)
        left++; 

        while (array[right].compareTo(pivot) > 0)
        right--;

        if (left<right) {
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }

    }

    temp = array[min];
    array[min] = array[right];
    array[right] = temp;

    return right;
}

输入:
安int[10]包含值 0 到 9 的数组，已打乱顺序。
因此，快速排序函数的调用方式如下: quicksort(nums, 0, nums.length-1)

输出(示例):

0
2
1
3
7
4
5
6
8
9

正如您所看到的，最终产品似乎正在走向良好的最终产品，但它在某个地方过早地停止了。

更新:
到目前为止提供的答案(包括已删除的答案)都不起作用。如果没有人能够发现该错误，是否有人可以将我重定向到 Java 通用算法的良好来源？

我什至可耻地尝试对上面提到的书中的快速排序算法进行纯粹的复制粘贴，当它编译和运行时，它产生了与上面相同的“几乎正确”的输出。然后我质疑这是否可能是我的输入数据，但不是。它只是一个整数的整数数组，没有重复项。据我了解，这是一个有效的候选者。

Answer 1

我能够使用以下分区函数进行快速排序以对一些测试数组进行排序。

private static <T extends Comparable<T>> int partition(T[] array, int min, int max) {

    int left, right;
    T pivot, temp;
    int middle = (min+max)/2;

    left  = min;
    right = max ;
    pivot = array[middle];

    while (left < right) {

        while (array[left].compareTo(pivot) < 0 && left < right)
            left++; 

        while (array[right].compareTo(pivot) > 0)
            right--;

        if (left<right) {
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
    return right;
}

我所做的更改是第一个compareTo 比较小于而不是小于或等于。这允许枢轴在阵列中移动。然而，这确实意味着数组不能包含重复项。我还删除了最后一个交换，因为我不知道它在做什么。

问题源于你如何处理枢轴。它实际上并没有正确地对数组进行分区。

<小时/>

这也有效并允许重复。

private static <T extends Comparable<T>> int partition(T[] array, int min, int max) {
    int left, right;
    T pivot, temp;
    int middle = (min+max)/2;

    left  = min + 1;
    right = max ;
    pivot = array[middle];

    // move partition element to min index
    temp = array[min];
    array[min] = array[middle];
    array[middle] = temp;

    while (left < right) {

        while (array[left].compareTo(pivot) <= 0 && left < right)
            left++; 

        while (array[right].compareTo(pivot) > 0)
            right--;

        if (left<right) {
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }

    }

    // move partition element to partition index
    temp = array[min];
    array[min] = array[right];
    array[right] = temp;
    return right;
}

我查了这本书的副本。该评论告诉您上次交换试图做什么。这使得我在请求时添加交换以将分区元素移动到最小索引的修复成为正确的修复。