0

誰かがこのソートアルゴリズムが何をするのか説明できますか? ロジックをたどることができず、再帰を使用しています。中間項を取って最初の項 (上から 8 行目) と交換するのは奇妙に思えます。また、最初の繰り返しでは++last = i、swap の呼び出しが無駄になります。

このコードはlast = left、を設定し、i = left + 1で swap() を呼び出します++last。これにより、 がlast等しくなりiます。

/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
    int i, last;

    if (left >= right) /* do nothing if array contains */
        return; /* fewer than two elements */

    swap(v, left, (left + right)/2); /* move partition elem */
    last = left;                     /* to v[0] */

    for (i = left + 1; i <= right; i++) /* partition */
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last); /* restore partition elem */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
    int temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}
4

1 に答える 1

4

コード内のコメントは非常に説明的です。最初に、「パーティション」要素が選択され、配列の先頭に移動されるため、後続のスワップはそれに触れません。次に、残りのすべての要素が部分的に並べ替えられるため、この 'partition' 要素を並べ替えられた配列の最後の場所に挿入できます。パーティション要素)。

アルゴリズムの詳細については、クイック ソートを参照してください。

于 2013-07-14T17:48:22.547 に答える