调试简单的快速排序实现

Question

我正在尝试使用 Java 实现快速排序算法，但它无法正确对我的输入数组进行排序。

我的输出：

1 7 8 9 28 22 45

预期输出：

1 7 8 9 22 28 45

public class Quicksort2 {
    public static void main(String[] args) {
        int[] arr = {22, 9, 8, 45, 28, 7, 1};
        quicksort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }

    static void quicksort(int[] arr, int low, int high) {
        int index = partition(arr, low, high);

        if (low < index - 1) {
            quicksort(arr, low, index - 1);
        }
        if (index > high) {
            quicksort(arr, index, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[(low + high) / 2];
        int i = low;
        int j = high;
        while (i <= j) {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;

            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        return i;
    }
}

Answer 1

用于递增 i / 递减 j 的内部 while 循环不遵守父 while 循环中设置的条件

i<=j

。

更改以下代码：

while(arr[i]<pivot) i++;
while(arr[j]>pivot) j--;

对此：

while(i<=j && arr[i]<pivot) i++;
while(i<=j && arr[j]>pivot) j--;

Answer 2

在我看来，快速排序中的第二个条件是错误的：

if(index>high) {
   quicksort(arr, index, high);
}

应该是

if (index < high) {
  quicksort(arr, index, high);
}

Answer 3

您的顶级递归条件有缺陷：

if (index > high) {
    quicksort(arr, index, high);
//...

这意味着数组的后半部分永远不会被排序。将上面两行替换为：

if (index < high) {
    quicksort(arr, index, high);
//...

或者更好的是，让你的

quicksort()

更紧凑：

static void quicksort(int[] arr, int low, int high) {
    if (low < high) {
        int index = partition(arr, low, high);
        quicksort(arr, low, index - 1);
        quicksort(arr, index, high);
    }
}