私はクイックソートアルゴリズムを実装しようとしています.これが私のコードです:
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 を、誰も変更せずに受け取る方法はありますか?