52

バケット ソートと基数ソートは近い関係にあります。バケット ソートは MSD から LSD に進みますが、基数ソートは両方の「方向」(LSD または MSD) に進むことができます。両方のアルゴリズムはどのように機能し、特にどのように異なるのでしょうか?

4

2 に答える 2

48

RadixSort両方の最初のパスBucketSortはまったく同じです。要素は、最大数の桁数に応じて、増分範囲 (たとえば、0 ～ 10、11 ～ 20、... 90 ～ 100) に配置buckets(または) されます。bins

ただし、次のパスでは、BucketSortこれらの「バケット」を並べ替えて、1 つの配列に追加します。ただし、RadixSortさらにソートせずにバケットを追加し、数値の 2 桁目 (10 の位) に基づいてバケットを「再バケット化」します。したがって、BucketSort は「密な」配列に対してより効率的ですが、RadixSort はまばらな (正確にはまばらではありませんが、間隔が空いた) 配列を適切に処理できます。

于 2011-01-06T15:19:45.010 に答える
26

Bucket Sort と Radix Sort は比較ソートではなく、一般的な考え方が似ているため、姉妹ソート アルゴリズムのようなものです。また、どちらも実装が少し抽象的です。

基数ソート:

  • 基数は基数( 2 進数、8 進数、10 進数など) を意味します。したがって、このソートは数値用です (文字列にも使用されます)。これは、各要素 E が e k ...e 2 e 1 e 0のような場合に機能します。ここで、e iはある範囲内にあります。(通常、0 から 10 進数で 0-9、ASCII 文字で 0-255 のような基数)

  • 次に、安定したサブソートアルゴリズムの k パスを使用します (安定している必要があります。そうでない場合、基数ソートは機能しません) 数値をソートします。このサブソート アルゴリズムは、通常、カウント ソートまたはバケット ソートでもありますが、基数ソート自体はできません。

  • 各パスですべての数字をシャッフルするため(k から 0 または 0 から k) 、最上位桁または最下位桁から開始できます。

  • これは、安定したソート アルゴリズムです。

バケットソート:

  • 配列を小さなグループまたはバケットに分割し、サブソート アルゴリズムまたはそれ自体への再帰呼び出しを使用して個別にソートし、結果を結合します。たとえば、チームのバケットに追加して選手を並べ替えてから、背番号で並べ替えたり、1 ～ 30 の範囲の数字を 1 ～ 10、11 ～ 20、21 ～ 30 の 3 つのバケットに並べ替えたりします。

  • 結合ステップは簡単です(マージソートとは異なります)。各バケットの要素を元の配列にコピーするか、各バケットの先頭を前のバケットの末尾に結合するだけです (リンクされたリストの場合)

  • 基数/ベースは、数値をソートする際のグループ/バケットのタイプ/インスタンスである可能性があります。したがって、MSD 基数はバケット ソートの変更されたインスタンスと考えることができます。

  • バケット ソートはインプレースではなく、安定したソート アルゴリズムです。ただし、バケット ソートの一部のバリエーションは安定していない可能性があります (安定していないサブソート アルゴリズムを使用している場合)。

于 2015-05-15T22:30:12.517 に答える