1

私はクイックソートアルゴリズムを実装しようとしています.これが私のコードです:

public class Sort {

int count = 0;

public void Partition(int A[], int l, int h) {

    if ((h-l) > 1) {

    count += (h-l) - 1;    

        int pivot = A[l];
        int i = l+1;
        int temp;
        int j;

        for (j = l + 1; j < h; j++) {

            if (A[j] < pivot) {  // SWAP
                temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                i++;
            }
            // else : j++            
        }

        temp = A[i-1];   
        A[i-1] = A[l];
        A[l] = temp;

        Partition(A, l, i-1);               
        Partition(A, i, A.length);

    }
  }
}

コードは入力配列をソートしますが、比較の数を数えると、元の比較の数よりもはるかに大きい数が得られます。ブレーク ポイントを追加し、コードに段階的に移動したところ、問題は最後の 2 行にあることがわかりました。パーティション(A、i、A、長さ);

2 番目の呼び出しで送信される 'i' は、最初のコードからの 'i' ではなく、関数 Partition への 1 番目の呼び出しの結果の i です。たとえば、コードが次の入力に対して最初に実行されるとき: 3 8 4 6 10 2 5 7 1 出力は次のようになります: 1 2 3 4 6 10 9 5 7 8 および i = 3. その後、Partition への最初の呼び出しは i (ここで、i は 3 に等しい) i の値を変更し続けます。最終的に完了すると、i の値は 3 とは異なり、別の間違った値が 2 番目の再帰呼び出しに送信されます。

私の質問は、2 つの呼び出しが同じパラメーター i を、誰も変更せずに受け取る方法はありますか?

4

2 に答える 2

1

これを試して。でソートしようとしないでくださいPartition。そこから、インデックスを返すだけiです (もちろん、戻り値の型を int に変更する必要があります)。次に、クイックソートを実装する別のメソッドを記述します。

public static void quicksort(int[] n, int left, int right){
if (left<right){
int pivotindex=Partition(n, left, right);
quicksort(n, left, pivotindex-1);
quicksort(n, pivotindex+1, right);}
}

これを次のようにテストしたところ、完全に機能しました。

public static void main(String[] args){
int[] n= new int[8];
n[0]=3;
n[6]=2;
n[1]=5;
n[3]=20;
quicksort(n, 0, n.length);
for (int i=0; i<n.length; i++){
    System.out.print(n[i]+",");
}
}
于 2013-07-22T20:52:16.007 に答える
0

pass-by-value をJava使用しているため、呼び出されたメソッドには参照がないため、最初の呼び出しで parameter の値を変更することはできません。 おそらく、2 番目の呼び出しが次の呼び出しになることを期待しているでしょう。ただし、最初の呼び出しがさらに 2 回呼び出されるため、次の実行のパラメーター値が予想とは異なるものになります。 i
PartitionPartitionPartition

また、メソッド名は小文字で始めてください。

于 2013-07-22T19:31:38.290 に答える