Pivot 未排序 [快速排序]

Question

我在这里有我的快速排序课程package week4;class QuickSort<T extends Comparable<? super T>> {    public void display(T[] array) {        int index;        for (index = 0; index < array.length - 1; index++)            System.out.print(array[index] + ", ");        System.out.println(array[index]);    }    private void swap(T[] a, int i, int j) {        T temp = a[i];        a[i] = a[j];        a[j] = temp;        display(a);    }    public void order(T[] a, int i, int j) {        if (a[i].compareTo(a[j]) > 0)            swap(a, i, j);    }    public void sortFirstMiddleLast(T[] a, int first, int mid, int last) {        order(a, first, mid); // make a[first] <= a[mid]        order(a, mid, last); // make a[mid] <= a[last]        order(a, first, mid); // make a[first] <= a[mid]    }    public int partition(T[] arr, int first, int last) {        int mid = (first + last) / 2;        sortFirstMiddleLast(arr, first, mid, last);        swap(arr, mid, last - 1);        int pivotIndex = last - 1;        T pivot = arr[pivotIndex];        int indexFromLeft = first + 1;        int indexFromRight = last - 2;        boolean done = false;        while (!done) {            while (arr[indexFromLeft].compareTo(pivot) < 0)                indexFromLeft++;            while (arr[indexFromRight].compareTo(pivot) > 0)                indexFromRight--;            if (indexFromLeft < indexFromRight) {                swap(arr, indexFromLeft, indexFromRight);                indexFromLeft++;                indexFromRight--;            } else                done = true;        }        // place pivot between Smaller and Larger subarrays        swap(arr, pivotIndex, indexFromLeft);        pivotIndex = indexFromLeft;        // Smaller = a[first pivotIndex-1]        // Pivot = a[pivotIndex]        // Larger = a[pivotIndex + 1..the last]        return pivotIndex;    }}我的问题是枢轴由于某种原因没有得到排序，我不知道为什么......我试图调试并尝试谷歌，但我无法弄清楚......

Answer 1

这似乎是快速排序算法的一个有点混乱的实现。

首先，我不认为拥有该sortFirstMiddleLast方法的意义。我们当然不能说在调用这个方法之后这三个数字在数组中的位置是正确的。例如，如果这三个数字恰好是数组中最大的三个数字会发生什么？它也不是快速排序算法的一部分。我会摆脱这种方法。

接下来，我们必须在交换元素时包括数组的第一个和最后一个元素，以确保它们位于枢轴的右侧。所以更换线

        swap(arr, mid, last - 1);

        int pivotIndex = last - 1;

        T pivot = arr[pivotIndex];

        int indexFromLeft = first + 1;

        int indexFromRight = last - 2;

和

        swap(arr, mid, last);

        int pivotIndex = last;

        T pivot = arr[pivotIndex];

        int indexFromLeft = first;

        int indexFromRight = last - 1;

接下来我们需要看一下这两个while循环：

            while (arr[indexFromLeft].compareTo(pivot) < 0)

                indexFromLeft++;

            while (arr[indexFromRight].compareTo(pivot) > 0)

                indexFromRight--;

第一个循环保证indexFromLeft在被排序的范围内终止，因为在某些时候arr[indexFromLeft]将是一个大于或等于主元的数字。如果枢轴恰好是最大数，则这包括枢轴本身，因为您将枢轴放在我们正在排序的子数组的末尾。

另一方面，如果arr[indexFromRight]小于（或等于）枢轴，则第二个循环将终止。但是，如果枢轴本身是正在排序的范围中的最小数字，indexFromRight则会偏离该范围。事实上，如果主元恰好是整个数组中最小的数，则无法阻止此循环从数组的开头掉下来并抛出 ArrayIndexOutOfBoundsException。

我们可以通过添加一个条件来避免这种情况，以防止indexFromRight超出我们正在排序的范围：

            while (indexFromRight > first && arr[indexFromRight].compareTo(pivot) > 0)

                indexFromRight--;

最后，您的代码似乎忽略了快速排序算法如何工作的一个关键方面：它是递归的。将枢轴放在正确的位置后，您必须递归地对它两侧的两个子数组进行排序。去做这个：

声明partitionreturnvoid而不是 an int，并删除该行return pivotIndex;。你没有对返回值做任何事情，所以我们不妨摆脱它。

partition将以下行添加到您的方法末尾以递归排序子数组：

    partition(arr, first, pivotIndex - 1);

    partition(arr, pivotIndex + 1, last);

将以下行添加到 的开头partition：

if (first >= last) { return; }

如果first == last那时您正在对 1 元素数组或子数组进行排序，则可以通过什么都不做进行排序。同样，如果first > last，要排序的子数组为空，也可以不做任何操作来排序。

Answer 2

尝试这样做：

public static int [] quickSort (int [] array, int first, int last){

        int pivot = array[last/2];

        while (!isSorted(array)) {

            int left = first;

            int right = last;

            while (true) {

                while (array[left] < pivot && left < last) {

                    left++;

                }

                while (array[right] >= pivot && right > first) {

                    right--;

                }

                if (array[left] > array[right]) {

                    swap(array, left, right);

                    System.out.println(Arrays.toString(array));

                }

                if (left >= right)

                    break;

                if (right - left == 1)

                    break;

            }

        }

    return array;

}

此方法检查数组是否已排序：

private static boolean isSorted(int [] array){

    for (int i = 0; i < array.length; i++){

        if (array[i] > array[i+1])

            return false;

    }

    return true;

}