24

本「Introduction to Algorithms」では、基数ソートの LSD (Least Significant Digit) バージョンについて言及しています。ただし、スタックオーバーフローで他の人が指摘しているように、MSD (Most Significant Digit) バージョンも存在します。そこで、それぞれのメリット・デメリットを知りたいです。私の推測では、LSD バージョンには MSD バージョンよりもいくつかの利点があると思いますが、よくわかりません。したがって、質問です。

4

3 に答える 3

11

リンクから取得すると、役に立つかもしれません: http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx (一番下)

LSD 基数ソートの最大の問題は、違いが最も少ない桁から開始することです。最上位の数字から始めることができれば、最初のパスは範囲全体のソートに大いに役立ち、その後の各パスは単純に詳細を処理します。MSD 基数ソートの考え方は、等しい値を持つすべての数字を独自のバケットに分割し、配列がソートされるまですべてのバケットで同じことを行うことです。当然、これは再帰アルゴリズムを示唆していますが、可変長アイテムをソートできるようになり、ソートされた配列を取得するためにすべての数字に触れる必要がないことも意味します。これにより、MSD 基数ソートがかなり高速になり、より便利になります。

于 2012-08-14T00:07:34.587 に答える
7

書籍Algorithmsで説明されているように、LSD と MSD はどちらも文字列配列の並べ替えアルゴリズムであり、比較ではなく、いわゆるキー インデックス付きカウントに基づいています。したがって、LSD と MSD は、従来のクイック ソートまたはマージ ソートとは実行時間が異なります。

Dzhabarov が述べたように、LSD と MSD の最大の違いは、MSD が最上位の数字または文字を最初に考慮することです。これは、本来、文字列内のすべての数字を反復処理せずに文字列を並べ替えます。これは利点です。ただし、MSD の再帰的な実装は、LSD よりも多くのスペースを使用します。

以下の表は、クイックソート、LSD、MSD の違いの一部を示しています。

algorithm    running time              extra space
quicksort    N(lgN)^2                  1
LSD          NW                        N
MSD          between N and NW          N + WR

ここで、N は配列の長さ、W は文字列の長さ、R は基数のサイズです。

PS: 本で述べたように、Java システムのソートは、LSD や MSD ではなく、高速な文字列比較を行う一般的なソート アルゴリズムを使用します。

于 2016-01-03T02:41:31.707 に答える
5

固定長がある場合、LSD は MSD よりも高速です。MSD は小さなファイルには遅すぎるため、小さなファイルに対して膨大な数の再帰呼び出しが必要です。

于 2016-02-27T14:40:19.653 に答える