算法就地阵列的重排序

-2

可能重复：
Reordering of array elements
Interview test - rearrange the array 算法就地阵列的重排序

我有其中3种语义元素（A，B，C）被存储在一个阵列形式如下：

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

这意味着ab和c不是实际的l值。第一个a可能是10，第二个1，第三个25，等等。一b和c表示，该计划将给予您看到“一”一定语义各项指标，同为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]

来源

2012-11-30 TravisG

这维基百科文章可以回答您的问题：[就地矩阵转]（HTTP：// EN .wikipedia.org /维基/在place_matrix_transposition）。 –

大多数排序算法，从冒泡到快速排序，在地方进行。 – dasblinkenlight

hmm .. quicksort，mergesort或任何其他的 – smk

存在与O（1）附加的内存使用情况的O（n.lgn）时间分而治之算法：

假定要重新排序波纹管的3n个大小的数组：

A = [1，N + 1,2n + 1，2中，n + 2,2n + 2，...，N，2N，3N]。

鸿沟A分成两个子阵列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]在就地与交换操作为O（n）。

T（N）= 2T（N/2）+ O（n）的= O（N LGN）

来源

2012-11-30 15:45:16 mhsekhavat

算法就地阵列的重排序

回答

相关问题