サイズ100のソートされていない値の配列（リストには100個の要素があります）が与えられ、各値は[0…1000]の範囲からランダムに抽出されます。与えられたリストを線形時間でソートするアルゴリズムを設計します（つまり、O（N）の最悪の場合のパフォーマンス）。
ヒント：値の範囲が事前にわかっているという事実を利用してください（つまり、1から1000まで）
これは私のクラスのHWの質問の1つです。彼は、上記を実行する関数の擬似コードを望んでいます。O（N）の最悪の場合のパフォーマンスを持つこれを行う関数を考えることはできません。
PS-基数ソートのような複雑なものは想定されていません。PSS-私はそれを行う方法についてのアイデアを手伝って欲しいだけです。宿題をしてくれる人を探していません。
これはjavabtwにあります。
ありがとう！
ビットマップソートを見てください。ソートされていない値のセットを配列のインデックスとして使用して機能し、O（N）時間で実行されます。
あなたが探しているのはカウントソートだと思います。各番号が発生した回数を追跡し、それらを順番に印刷します。
これは通常、最初のアルゴリズムクラスでこれについて教えるアルゴリズムです：http：//en.wikipedia.org/wiki/Radix_sort
ニックは正しいです（彼に信用を与えてください-コメントフィールドに収まらないので、私は答えているだけです）。
1,001個の要素がすべてゼロに初期化された配列を定義します。一度に100個の値を読み取り、読み取っている値と同じインデックスを持つ配列要素をインクリメントします。これを100回実行すると、1,001要素の配列（ほとんどはまだゼロ）が作成され、0番目の配列要素の値で指定された回数だけ0を出力し、次に1を何回も出力します。これは遅いように聞こえますが、O（n）アルゴリズムであるため、他のどの並べ替え方法よりも高速ですが、入力がすべて範囲内の整数であることがわかっている場合にのみ機能します。 0から1,000（合計1,001の可能性）。
ええ、「カウントソート」はO（n）+ O（N）（n = 100＆N = 1000）になります。しかし、n log（n）よりも優れていると主張するすべてのスキームと同様に、メモリの拡張コストを考慮すると、O（N）コンポーネントは実際にはN log Nコンポーネントであるため、「チート」します。メモリパフォーマンスはNをメモリサイズに記録します。問題の特定のプロセッサでは、メモリサイズが固定されているため、logN係数が埋め込まれているだけです。
この場合のソートのカウントのコストは、O（N + Nsqrt（N））= O（N ^ 3/2）のようです。@Daniel_Williamsが言ったように、これはradix_sortを使用して改善できると思います。たとえば、MITオープンコースの講義5を参照してくださいhttps://www.youtube.com/watch?v=0VqawRl3Xzs