0

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

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);
    }
}

拜托，我也希望能纠正我算法中的任何其他低效率问题。谢谢

4

2 回答 2

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);
}
于 2012-04-10T17:11:18.997 回答
0

使用您拥有的签名为快速排序调用创建一个包装器，该签名调用另一个类似的签名，quicksort(A, i, j)并且您来自包装器的调用将是quicksort(A, 0, n).

于 2012-04-10T16:37:21.867 回答