0

私はクイックソートアルゴリズムを実装しており、入力配列をピボットでうまく分割しました。問題は、同じ入力配列を使用して、配列の最初の部分と 2 番目の部分を再帰的に並べ替える (つまり、範囲を指定する) 方法に混乱していることです。以下は私の実装です

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 に答える