1

私は、数の順序付けられたシーケンスの配列をソートする部分である複雑なアルゴリズムを実装しています。アルゴリズム全体はnlog（n）の複雑さである必要があるため、この部分は同じかそれ以上である必要がありますが、これを行う方法がわかりません。

例があります。シーケンスの配列があります：

(0)
(0,1)
(0)
(0,5)
(2,4)
()
(0,5)
()
(2,4)
(1,3,4)

最終的な並べ替えは次のようになります。

()
()
(0)
(0)
(0,1)
(0,5)
(0,5)
(1,3,4)
(2,4)
(2,4)

重要な注意事項がいくつかあります。

  • ソートは辞書式順序です
  • シーケンスは順序付けられていますが、連続性の保証はありません
  • 空のシーケンスもあります
  • 同一のシーケンスがたくさんあります
  • シーケンスの長さは0から数百で、それ以上はありません
  • 配列の長さは100kで、おそらくそれ以上になることはありません
  • 最終的な実装はC++で行われますが、今ではおそらく重要ではありません

並べ替えの最良の方法を教えてください。どうもありがとう

4

3 に答える 3

2

radix sortこの場合、最初にシーケンスを右端のアイテム (たとえば 100 番目のアイテム) でソートし、そのようなアイテムが存在しない場合は (たとえば、-1 が表示される場合) として設定し、min possible value - 1次にこのソートされたシーケンスを次のようにソートします右端から 2 番目の項目に移動し、この方法を続けます。

また、シーケンス内の項目がすべて 1..k の間にある場合 (この場合、1..9 の間にあることがわかりますcounting sort)、O(n) で並べ替えるために使用します。カウント並べ替えを使用できる場合、並べ替え時間は O( n) それ以外の場合、ソート時間は O(n log n) です。

于 2011-02-06T10:20:45.413 に答える
1

クイックソートを使用する場合、ソート アルゴリズムは O(n log n) になります。2 つの項目をどのように比較する必要があるかは、並べ替え自体の複雑さとは無関係であり、独自の複雑さ (おそらく O(m)) があります。

于 2011-02-06T09:57:21.387 に答える
0

GPLv3 コードをプロジェクトに統合できる場合は、GNU Sortから始めるのがよいでしょう。少なくとも、サンプル入力で実行したところ、サンプル出力が得られたので、すぐに間違っているわけではありません。

于 2011-02-06T10:00:18.310 に答える