5

ご存知のように、クイックソートでは Lomuto-Partition を使用できます。私は多くの参考文献をチェックしましたが、それらのほとんどすべてが次の実装を思いつきました:

int L_partition(int *a, int l, int r)
{
    int i, j, p, t;

    p = a[r];
    i = l - 1;

    for(j =l; j <= r-1; j++) {
        if(a[j] <= p) {
            i++;

            t = a[j];
            a[j] = a[i];
            a[i] = t;
        }
    }

    t = a[i+1];
    a[i+1] = a[r];
    a[r] = t;

    return i+1;
}

私の質問は、なぜiがl-1で始まり、すべてのi+1のものを持っているのですか? lから始めるだけでいいと思います。以下のプログラムをテストします。そして、上記と同じ結果が得られます。これは、上記のものよりもはるかに簡単です。

int L_partition2(int *a, int l, int r)
{
    int i, j, p, t;

    p = a[r];
    i = l;

    for(j = l; j <= r-1; j++) {
        if(a[j] <= p) {
            t = a[j];
            a[j] = a[i];
            a[i] = t;

            i++;
        }
    }

    t = a[i];
    a[i] = a[r];
    a[r] = t;

    return i;

}
4

1 に答える 1

0

の使用法をシフトしているだけですi。

あなたのものは最初から有効であり、元のバージョンはスワップの前にそれをインクリメントするため、スワップ後に i をインクリメントしていることに注意してください。しかし重要なことは、スワップは常に同じ要素を使用するということです (あなたのバージョンとオリジナルで)。

于 2013-10-02T09:34:05.080 に答える