使用Java中的Hoare分区对数组进行排序的快速排序算法

Question

我正在尝试通过快速排序对数组进行排序：

int[] arr = {25,23,21,29,28,22,24,27};

我的快速排序功能：

public static void quickSort(int[] arr) { // sorts array using quick sort algorithm
    if (arr[0] < arr[arr.length-1]) {
        int s = hoarePartitioning(arr);
        quickSort(Arrays.copyOfRange(arr, 0, s-1));
        quickSort(Arrays.copyOfRange(arr, s+1, arr.length));
    }
}

我使用了Hoare分区：

public static int hoarePartitioning(int[] arr) {
    int pivot = arr[0];
    int i = 0;
    int j = arr.length;
    do {
        do {i++;} while(pivot >= arr[i] && i < arr.length);
        do {j--;} while(pivot <= arr[j] && j >= 0);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }while(i <= j);

    int temp = arr[i];  //undo last swap when i >= j
    arr[i] = arr[j];
    arr[j] = temp;

    temp = arr[0];
    arr[0] = arr[j];
    arr[j] = temp;

    return j;
}

但是，当我打印出数组时，结果是：

22 23 21 24 25 28 29 27 

我的Hoare分区功能工作正常，但我仍然不明白为什么数组未排序。我在这里做错了什么？谢谢。

Answer 1

quicksort方法错误。

全部以此开头：

    quickSort(Arrays.copyOfRange(arr, 0, s-1));
    quickSort(Arrays.copyOfRange(arr, s+1, arr.length));

每次递归时，都会为左右两个子数组创建一个新数组，（尝试）对新数组进行排序，然后将它们扔掉。

还有其他一些问题：

1. if测试看起来不正确。在这种情况下为什么要跳过对数组/子数组的排序？

2. 子数组的上限计算看起来不正确； s - 1是一个包含边界，但是arr.length是一个排除边界。其中之一一定是错误的。