6

のように、しばらくの間単調に増加し、その後減少し、再び増加する...などの配列があります[1,2,3,4,5,3,1,-1,-3,2,5,67,90,8,7,3,0]。この配列をソートする最良の方法は何でしょうか? K-Way Merge Sort実装の詳細は提供されていませんが、Stackoverflow のいくつかの関連する質問が提案されました。

では、それをソートする理想的な方法は何でしょうか? O(N*log N)によって与えられた古き良き方法よりもはるかに優れたパフォーマンスを提供しquicksort、その使用に値する巧妙な方法はありますか? やるべきことがある場合K-Way Merge Sortは、実装の詳細を提供してください。インターネット上で見つけることができませんでした!

4

2 に答える 2

1

前処理を伴う自然なマージソートはO（n）でそれを行うと思います。

  1. 降順のサブ配列の順序を逆にする - 合計 O(n)
  2. 自然なマージソートを行う - O(n): http://www.algorithmist.com/index.php/Merge_sort#Natural_mergesort
于 2012-10-28T00:47:08.623 に答える
1

自然な実行を利用するTimsortが必要です。

于 2012-10-28T00:00:11.793 に答える