1

整数を含む配列が与えられ、各整数が最終位置から最大で n 位置離れている場合、最適な並べ替えアルゴリズムは何でしょうか?

私はこれについてしばらく考えていましたが、この問題に対処するための良い戦略が思い浮かびません。誰かが私を案内してもらえますか？

4

4 に答える 4

7

(サイズ N の) リストを 2n 個のサブリストに分割します (0 から始まるインデックスを使用):

リスト 0: 要素 0、2n、4n、...
リスト 1: 要素 1、2n+1、4n+1、...
...
リスト 2n-1: 要素 2n-1、4n-1、...

これらの各リストは明らかにソートされています。

次に、これらのリストをマージします (一度に 2 つのリストを繰り返しマージするか、これらの各リストの 1 つの要素で最小ヒープを使用します)。

それで全部です。時間計算量は O(N log(n)) です。

これは Python では簡単です。

>>> a = [1, 0, 5, 4, 3, 2, 6, 8, 9, 7, 12, 13, 10, 11]
>>> n = max(abs(i - x) for i, x in enumerate(a))
>>> n
3
>>> print(*heapq.merge(*(a[i::2 * n] for i in range(2 * n))))
0 1 2 3 4 5 6 7 8 9 10 11 12 13
于 2012-04-05T23:52:58.720 に答える
1

ヒープ ソートは、最初はランダムな要素の配列/コレクションに対して非常に高速です。疑似コードでは、この並べ替えは次のように実装されます。

# heapify
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

「ほぼソート済み」または「少数のユニーク」などのさまざまなケースでは、アルゴリズムの動作が異なり、より効率的になります。さまざまな場合のアニメーションを含むアルゴリズムの完全なリストについては、このすばらしいサイトを参照してください。

これが役立つことを願っています。

Ps。ほぼソートされたセット（上記のコメントのとおり）の場合、挿入ソートが勝者です。

于 2012-04-05T19:10:44.930 に答える
0

コムソートを使用することをお勧めします。最大距離（またはそのあたり）に等しいギャップサイズから始めてください。O（n log n）（またはあなたの場合はO（n log d）、ここでdは最大変位）、理解しやすく、実装しやすく、要素が予想以上に変位した場合でも機能することが期待されます。保証された実行時間が必要な場合は、ヒープソートのようなものを使用できますが、過去には、スペースのオーバーヘッドや計算時間は通常それだけの価値がなく、他のほとんどのものを実装することになります。

于 2012-04-05T19:28:49.783 に答える