タイトルが示すように、基数ソートは唯一の非比較ソートアルゴリズムですか? 私の推測ではイエスです。
6139 次
2 に答える
6
いいえ - とりわけ、カウントソートとバケットソートもあります。詳細については、ウィキペディアの記事を確認してください。
于 2011-05-12T20:26:56.820 に答える
1
比較を使用しないことで、任意のセットをソートできます。
プロセスは
- 管理可能な配列に記録するために処理できる入力ドメイン M の管理可能なサイズを決定します。文字 (8 ビット) の場合、ドメインは 0 ～ 255 になります。
- 入力を規則正しい方法で配列に分割します。
- 入力がまだ完全に考慮されていない場合、つまり M のすべてのビットが考慮されていない場合は、繰り返してすすぎます。
たとえば、32 ビット、M、整数の並べ替えは次のように実行できます。
- 最初の 8 ビットを見て、(参照、ポインタ、または言語で使用できるもの) を 8 ビットの範囲に入れます。それらを配列 [0-255] に入れます。これで、値の粗い (球場) 順序付けができました。
- 次の 8 ビットを見て、それらを同様の配列に入れ、最初の順序への参照を保持します。次の 8x2 ビットも同様に処理されます。抽出するには、最初のセットのリンクをたどります。
基数ソートは数字を使用し、(MSB から LSB) と (LSB から MSB) の 2 つのバリアントがあります。
カウントソートは最初のステップのみを使用します
バケットソートは通常、カウントソートと比較ソートの組み合わせを指す場合に言及されます。
興味深いことに、かなりの数のユースケースで、比較ソートが不足しています。
于 2011-05-12T20:52:43.213 に答える