20

manページには何も書かれていないので、stdlibの古き良きqsort関数は安定していないと思います。これは私が話している機能です：

   #include <stdlib.h>
   void qsort(void *base, size_t nmemb, size_t size,
              int(*compar)(const void *, const void *));

比較関数を変更して、比較しているアドレスも含めると、安定すると思います。あれは正しいですか？

例えば：

int compareFoos( const void* pA, const void *pB ) {
    Foo *pFooA = (Foo*) pA;
    Foo *pFooB = (Foo*) pB;

    if( pFooA->id < pFooB->id ) {
        return -1;
    } else if( pFooA->id > pFooB->id ) {
        return 1;
    } else if( pA < pB ) {
        return -1;            
    } else if( pB > pA ) {
       return 1;
    } else {
       return 0;
    }
}
4

3 に答える 3

32

いいえ、残念ながらそれに頼ることはできません。配列があるとします (各レコードの 2 つのフィールドはチェックに使用されますが、最初のフィールドのみが並べ替えに使用されます)。

BBBB,1
BBBB,2
AAAA,3

クイックソートは、BBBB,1 と AAAA,3 を比較し、それらを交換して、次のようにします。

AAAA,3
BBBB,2
BBBB,1

次のステップで BBBB,2 と BBBB,1 を比較すると、キーは同じになり、BBBB,2 のアドレスは BBBB,1 より小さいため、スワップは発生しません。安定した並べ替えの場合、次のようになるはずです。

AAAA,3
BBBB,1
BBBB,2

これを行う唯一の方法は、ポインターの開始アドレス (現在のアドレスではない)をアタッチし、それと他のキーを使用してソートすることです。そうすれば、元のアドレスはソート キーのマイナー部分になるため、ソート プロセス中に2 つの行がどこに移動するかに関係なく、BBBB,1最終的には前になります。BBBB,2BBBB

于 2009-02-25T04:16:31.710 に答える
10

標準的な解決策は、元の配列の要素へのポインターの配列を作成 (つまり、メモリを割り当てて埋める) することです。この新しい配列は、余分なレベルの間接化を使用し、それらが指しているものがqsortポインター値の比較に戻ります。は同じ。このアプローチには、元の配列をまったく変更しないという潜在的な副次的な利点があります。ただし、元の配列を最後に並べ替えたい場合は、後でポインターの配列の順序と一致するように並べ替える必要があります。qsort戻り値。

于 2011-05-24T04:08:47.907 に答える