实现快速排序算法但遇到问题

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);
//...

这意味着数组的后半部分永远不会被排序。

将上面的“大于”符号改为“小于”。

或者更好的是，让你的

quicksort()

更紧凑：

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