[解決済み] 整数が [1,100] の範囲にあるとき、100万個の整数を最も速くソートする方法は何ですか？

質問

注意事項 Radixソート、バケットソート、カウントソートについて考えてみました。

大きなO(n)を実現する方法はありますか？

どのように解決するのですか？

を使用することができます。 カウントソート .

カウントソート（ウルトラソートや数学ソートと呼ばれることもあります）は、（バケットソートと同様に）ソート対象の配列（配列A）の数値の範囲を知っていることを利用したソートアルゴリズムです。

ここで、n と k はそれぞれ配列 A（入力配列）と C（計数配列）の長さである。このアルゴリズムが効率的であるためには、k は n よりもずっと大きくてはならない。

この場合、kは100で、nは1000000です。