0

ほぼソートされた 30 億の整数の配列があるとします。
(「クラシック」アルゴリズムの中から)どのソートアルゴリズムがより適切でしょうか?
リストが完全にランダムだったらどうですか?

4

3 に答える 3

1

入力が（ほぼ）ソートされている場合、線形時間を必要とする挿入ソートの使用を検討してください。クイックソートとマージソートは、入力がソートされていても O(n log n) の時間計算量があります。

于 2012-09-03T11:07:29.563 に答える
1

標準の UNIX の sort() 呼び出しで使用されるものであり、それを変更する制約 (最小時間や最小メモリなど) を提供していないため、両方にマージソートを使用します。

于 2012-09-02T19:02:58.073 に答える
1

さまざまな用途の並べ替え方法を比較した「一言で言えばアルゴリズム」の著者によると、あなたの基準は InsertionSort を支持します。見る;

http://my.safaribooksonline.com/book/software-engineering-and-development/algorithms/9780596516246/sorting-algorithms/criteria_for_choosing_a_sorting_algorit

于 2012-09-03T11:11:47.367 に答える