java - 对快速排序算法感到困惑

Question

我正在实现快速排序算法，并已成功围绕枢轴对输入数组进行分区。问题是，我对如何使用相同的输入数组对数组的第一部分和第二部分(即指定范围)进行递归排序感到困惑。下面是我的实现

class QuickSort {

    int i; 
    int l = 0;

    public void quicksort(int A[], int n) {

        if (n == 1) {
            return;
        } else {
            partition(A, 0, n);
//----Confused as from this point
            quicksort(A, A[i]);

            //Recursively sort both parts of the array
        }
    }

    public int partition(int A[], int l, int r) {
        int p = A[l];//Choose pivot
        i = l + 1;
        //Partition around A through P
        for (int j = i; j < r; j++) {
            if (A[j] < p) {
                swap(A, i, j);
                ++i;
            }
        }
        swap(A, l, i - 1 );
        return i;
    }

    public void swap(int A[], int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    public void display(int A[]){
        for (int i = 0; i < A.length; i ++){
            System.out.print(A[i] + " ");
        }
    }
}
class QuickSortApp{
    public static void main(String args[]){
        QuickSort quick = new QuickSort();
        int A[] = {6,2,7,8,4,3,5};
        quick.quicksort(A,  A.length);
        quick.display(A);
    }
}

请纠正我的算法中的任何其他低效率问题。谢谢

Answer 1

将 quicksort() 签名更改为 quicksort(int[] A, int begin, int end)

因为，您实际上在 partition() 中进行了排序。我要做的是这样的:

if (end-begin <= 1) {
    return;
} else {
    int pivot = partition(A, begin, end);
    quicksort(A, begin, pivot);
    quicksort(A, pivot, end);
}