java - Pivot 未排序 [快速排序]

问题描述

我在这里有我的快速排序课程

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;
    }
}

public class Project1B {

    public static void main(String args[]) {
        QuickSort<Integer> ob = new QuickSort<Integer>();

        Integer[] arr = { 10, 7, 8, 9, 1, 5 };

        int n = arr.length;

        ob.partition(arr, 0, n - 1);

        System.out.println("sorted array");
        ob.display(arr);
    }
}

我的输出是这样的..：

8、7、10、9、1、5

8、7、5、9、1、10

5、7、8、9、1、10

5、7、1、9、8、10

5、7、1、8、9、10

排序数组

5、7、1、8、9、10

我的问题是枢轴由于某种原因没有得到排序，我不知道为什么......我试图调试并试图用谷歌搜索，但我无法弄清楚......

标签： javaquicksort

解决方案

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

首先，我看不出拥有该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--;

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

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

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

    partition(arr, first, pivotIndex - 1);
    partition(arr, pivotIndex + 1, last);

将以下行添加到的开头partition：
```
if (first >= last) { return; }
```
如果first == last那时您正在对 1 元素数组或子数组进行排序，则可以通过什么都不做来进行排序。类似地，如果first > last，要排序的子数组是空的，也可以不做任何事情进行排序。

java - Pivot 未排序 [快速排序]

问题描述

解决方案

推荐阅读