algorithm - 配列のインプレース並べ替えのアルゴリズム

Question

重複の可能性:
配列要素の
並べ替え インタビュー テスト - 配列の並べ替え

3 つのセマンティック要素 (a、b、c) が次の形式で格納されている配列があります。

[a][b][c][a][b][c][a][b][c]...

これは、ab と c が実際の値ではないことを意味します。最初の a は 10、2 番目は 1、3 番目は 25 などです。ab and c は、「a」が表示されるすべてのインデックスに、b と c の場合と同じように、プログラムが特定の意味的な意味を与えることを示しています。

次の形式になるように並べ替えたいと思います。

[a][a][a]...[b][b][b]...[c][c][c].... 

一時的な「バッファ」配列を使用せずに、これを「インプレース」で行う方法はありますか?

値の例:

開始配列:

[11][5][3][284][123123][841823][0][11][22]

次のように並べ替える必要があります。

[11][284][0][5][123123][11][3][841823][22]

Answer 1

O(1) の追加メモリ使用量を持つ O(n.lgn) 時分割統治アルゴリズムがあります。

以下の 3n サイズの配列を並べ替えたいとします。

A=[1,n+1,2n+1, 2,n+2,2n+2, ... , n,2n,3n].

A を 2 つのサブ配列 A1 と A2 に分割します。A1 には 1 から 3*[n/2] までの番号が付けられたインデックスが含まれ、A2 には 3*[n/2]+1 から 3n までのインデックスが含まれます。A1 と A2 (インプレース) を再帰的に並べ替えます。次に、A は 6 分割された配列 [p1,p3,p5,p2,p4,p6] のようなものになり、各部分は結果要素の正しく順序付けられたサブ配列であり、それらを [p1,p2, p3,p4,p5,p6] in O(n) in-place with swap operations.

T(n)=2T(n/2)+O(n)=O(n lgn)