Java-实现QuickSort[副本]

Question

我在学数据结构和算法。所以我尝试实现了快速排序算法。

public static void main(String[] args) {
    // TODO Auto-generated method stub

    int[] arr = new int[] { 10, 16, 8, 12, 15, 6, 3, 9, 5 };

    quickSort(0, arr.length - 1, arr);
}

public static void quickSort(int start, int end, int[] arr) {

    if (start < end) {

        int partitionIndex = partition(start, end, arr);
        quickSort(start, partitionIndex - 1, arr);
        quickSort(partitionIndex+1, end, arr); // When passing partitionIndex+1 in the swap method it throws index out of bound exception

        System.out.println(Arrays.toString(arr));
    }   

}

public static int partition(int start, int end, int[] arr) {

    int pivot = arr[end];
    int pIndex = start;

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

        if (arr[i] <= pivot) {
            swap(i, pIndex, arr);
            pIndex++;
        }
    }

    swap(pIndex, end, arr);
    return pIndex;

}

private static void swap(int i, int index, int[] arr) {

    int temp = arr[i];
    arr[i] = arr[index]; // index out of bound exception is thrown
    arr[index] = temp;

}

在执行递归调用QuickSort(PartitionIndex+1,end,arr）；时，在swap方法中，它会抛出索引越界异常。因为没有这样的索引来检索/存储值。有谁能帮我解决这个问题吗？

Answer 1

我假设您试图实现来自维基百科的Lomuto分区方案。如果是这种情况，您的代码中有2个错误，都在partition方法的for循环中：

1. 开始索引:

您的算法每次从0开始。这导致了IndexOutOfBoundsException，因为它交换了pindex，后者在末尾是array.lengts。如果您修复了这一点，异常将会消失，但您的排序结果将是[3,5,8,10,12,15,6,16,9]，这显然不是完美排序的。

这里的错误是，每次都缺少最后一次迭代，因为您的结束条件是i 将其更改为 i 或 i<=end-1，您将得到一个完美的结果：

<代码>[3,5,6,8,9,10,12,15,16]

下面是固定的partition方法和您的quicksort方法：

java prettyprint-override">public static void quickSort(int start, int end, int[] arr) {
    if (start < end) {
        int partitionIndex = partition(start, end, arr);
        quickSort(start, partitionIndex - 1, arr);
        quickSort(partitionIndex + 1, end, arr);
    }
}

public static int partition(int start, int end, int[] arr) {
    int pivot = arr[end];
    int pIndex = start;
    for (int i = start; i < end; i++) {
        if (arr[i] < pivot) {
            swap(pIndex, i, arr);
            pIndex++;
        }
    }
    swap(pIndex, end, arr);
    return pIndex;
}