0

これは私を夢中にさせています。これが1回限りのエラーの原因であることはわかっていますが、何らかの理由で、パーティション関数が正しくパーティション分割されていません. 私は何を間違っていますか？

public static int partition(int numbers[], int lhs, int rhs) {
    int pivot = numbers[(rhs - lhs) / 2];
    int lIndex = lhs - 1;
    int rIndex = rhs + 1;

    while (true) {
        while (numbers[++lIndex] < pivot);
        while (numbers[--rIndex] > pivot);

        if (lIndex > rIndex) break;

        int temp = numbers[lIndex];
        numbers[lIndex] = numbers[rIndex];
        numbers[rIndex] = temp;
    }

    return lIndex;
}
4

2 に答える 2

2

次のようにピボット（あなたの場合は中間点）を見つける方が良いです：

int pivot = numbers[lhs + (rhs - lhs) / 2];

lhs と rhs が十分に高い場合、lhs+rhs が整数オーバーフローを引き起こすのを防ぎます。

于 2013-08-11T09:42:04.437 に答える
1

ここに 1 つの問題があります。

int pivot = numbers[(rhs - lhs) / 2];

lhs= 100 と= 120と仮定しrhsます。上記は要素 (120 - 100) / 2 = 10 をピボットとして選択します!

あなたは次のようなものが欲しいと思います

int pivot = numbers[(rhs + lhs) / 2];

少なくとも、分割しようとしている範囲内からピボットを選択します!

于 2013-08-11T00:20:32.790 に答える