1

Partition が呼び出されるたびに、比例配列の中央値がピボットとして使用されるように、(Java で) QuickSort を変更したいと考えています。

k 番目に小さい要素 (この場合は中央値) を返す Java の中央値選択アルゴリズムがあります。Java には、すべて単独で機能し、配列をソートする大量のクイックソート アルゴリズムがあります。残念ながら、上記を達成するためにこれら2つを組み合わせることはできません...試してみると、通常、スタックオーバーフローエラーが発生します。

誰かコードを見せて、それがどのように行われるかを確認できますか?

ありがとう

編集:たとえば、これは私が使用しようとした中央値選択アルゴリズムです。

public int quickSelect(int[] A, int p, int r, int k) {
    if (p==r) return A[p];
    int q = Partition(A,p,r);
    int len = q-p+1;

    if (k == len) return A[q];
    else if (k<len) return Select(A,p,q-1,k);
    else return Select(A,q+1,r,k-len);
}

public int partition(int[]A, int p, int r) {
    int x = A[r];
    int i = p-1;
    for (int j = p; j<=r-1; j++) {
        if (A[j] <= x) {
            i++;
            swap(A,i,j);
        }
    }
    swap(A,i+1,r);
    return i+1;
}

それ自体は機能しますが、使用するピボットを返すためにクイックソートのパーティション関数を介して quickSelect を呼び出そうとすると、機能しません。明らかに私は何か間違ったことをしているのですが、私には何がわかりません。残念ながら、インターネット上では、疑似コードであっても、中央値選択とクイックソートを組み合わせるアルゴリズムは見つかりませんでした。

4

4 に答える 4

0

あなたはこれを使うことができます...

int Select(int array[],int start, int end,int k){

if(start==end){
    return start;
}

int x=array[end];
int i=start-1;
for(int j=start;j<=end-1;j++){
    if(array[j]<x){
        i++;
        Swap(array+i,array+j);
    }
}
i++;
Swap(array+i,array+end);

if(i==k){
    return i;
}
else if(i>k){
    return Select(array,start,i-1,k);
}
else{
    return Select(array,i+1,end,k);
}

}

Selectは、配列内のk番目に小さい要素で配列を分割します。

于 2013-01-20T11:29:13.567 に答える
0

であることに注意してPARTITIONください。pivotA[r]

public int QUICKSORT2(int[] A, int p, int r) {
    if (p<r) {
        int median=Math.floor((p + r) /2) - p + 1
        int q=SELECT(A, p, r, median)
        q=PARTITION2(A, p, r, q)
        QUICKSORT2(A, p, q-1)
        QUICKSORT2(A, q+1, r)
    }
}

public int PARTITION2(int[]A, int p, int r, int q) {
    int temp = A[r];
    A[r]=A[q];
    A[q]=temp;
    return PARTITION(A, p, r)
}
于 2012-07-18T06:15:21.723 に答える
0

中央値を取得する標準的な方法は、データを並べ替えることです。そして、中央値で分割してデータを並べ替えたいとします。これは私には非常に鶏と卵のようです。

中央値で分割/ピボットする理由を詳しく説明していただけますか?

于 2012-05-15T23:14:26.610 に答える
0

あなたが探しているのは、選択アルゴリズムです。疑似コードへのリンクは次のとおりです。

リンクから：

コンピューター サイエンスでは、選択アルゴリズムは、リスト内の k 番目に小さい数を見つけるためのアルゴリズムです。

中央値を見つけるには、リスト内の k=floor((n+1)/2) 最小数を見つけます。ここで、n はリストのサイズです。

于 2012-05-15T23:52:38.563 に答える