24

[0..n ^ 3-1]の範囲のn個の整数の入力セットが与えられた場合、線形時間ソートアルゴリズムを提供します。

これは木曜日の私のテストのレビューであり、この問題にどのように取り組むべきかわかりません。

4

8 に答える 8

24

関連するソートも見てみましょう: pigeonhole sortまたはcounting sort、およびPukku で言及されている基数ソート。

于 2009-04-14T22:29:39.153 に答える
23

基数ソートを見てください。

于 2009-04-14T22:26:22.390 に答える
12

人々が「ソート アルゴリズム」と言うとき、「比較ソート アルゴリズム」を指していることがよくあります。これは、「これはそれよりも大きいか小さいか」を尋ねることができることのみに依存するアルゴリズムです。したがって、データについてこの 1 つの質問をすることに制限されている場合、n*log(n) を超えることはありません (これは、データ セットの n 階乗の可能な順序付けの log(n) 検索を実行した結果です)。 .

「比較ソート」の制約を回避し、データの一部についてより洗練された質問をすることができれば、たとえば「このデータの基数 10 は何ですか」など、線形時間ソート アルゴリズムをいくつでも思いつくことができます。より多くのメモリを必要とするだけです。

これは時間空間のトレードオフです。比較ソートは RAM をほとんどまたはまったく必要とせず、N*log(n) 時間で実行されます。基数ソート（たとえば）は、O（n）時間AND O（log（基数））メモリで実行されます。

于 2009-04-14T23:46:16.580 に答える
3

n=2 で数値が一意の場合は、非常に簡単です。

  • ビットの配列を構築します (2^31-1 ビット => ~256MB)。それらをゼロに初期化します。
  • 入力を読み取り、表示される値ごとに、配列内のそれぞれのビットを 1 に設定します。
  • 配列をスキャンし、ビット セットごとに、それぞれの値を出力します。

複雑さ => O(2n)

それ以外の場合は、基数ソートを使用します。

複雑さ => O(kn) (できれば)

于 2009-04-14T22:35:25.877 に答える
3

ウィキペディアには、非常に多くの異なる並べ替えアルゴリズムとその複雑さが示されています。あなたはそれらをチェックアウトしたいかもしれません

于 2009-04-14T22:35:42.617 に答える
2

数値は、各桁が 0 から n-1 までの 3 桁の数値と考えてください。これらの数値を基数ソートでソートします。桁ごとに、合計実行時間が Theta(n) に対応するように、Theta(n+n) 時間かかるカウント ソートの呼び出しがあります。

于 2012-11-14T17:37:01.827 に答える
2

限られた範囲の数値のセットは、RANGE ビットのビットマップで表すことができます。この場合、500 MB のビットマップなので、巨大なリスト以外の場合は、Radix Sort を使用したほうがよいでしょう。数値 k に遭遇したら、bitmap[k] = 1 に設定します。リストを 1 回トラバーサルする O(N)。

于 2009-04-14T22:33:23.887 に答える
-2

同様のアルゴリズムが可能です:

M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];

線形の複雑さのための唯一の可能なアルゴリズムですが、ram (N - 配列要素の数、k -- 要素の len) ごとに O(k*N) の複雑さがあります。

于 2009-04-15T00:06:21.510 に答える