java - Quicksort Java 代码进入无限循环

Question

当我尝试运行下面的快速排序代码时，它会进入无限循环。最后一次迭代将进入无限循环。

class QuickSort {
    public static void main(String[] args) {
        int arr[] = {10, 7, 8, 9, 1, 5,2};
        QuickSort ob = new QuickSort();
        ob.sort(arr, 0,arr.length-1);
        for(int s:arr){
            System.out.print(" "+s);
        }
    }
    int partition(int[] arr,int l,int h){
        int piv = arr[h];
        int i=l-1;
        for(int j=l;j<=h-1;j++){
            if(arr[j] <= piv){
                i++;
                int temp = arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        int tp = arr[i+1];
        arr[i+1]=arr[h];
        arr[h]=tp;
        return i+1;
    }

    void sort(int[] arr,int l,int h){
        while(l<h){
            int p = partition(arr, l, h);
            sort(arr, l, p-1);
            sort(arr, p+1, h);
        }

    }
}

请帮忙看看哪里出了问题。

Answer 1

使用 if 条件代替 while 循环，如下所示。

if(l<h){
        int p = partition(arr, l, h);
        sort(arr, l, p-1);
        sort(arr, p+1, h);
    }

无需在无限 while 循环中递归调用 sort。循环是无限的，因为 l 和 r 在算法中永远不会改变。

希望这有帮助:)