-2

可能重复：
数组元素的重新排序
面试测试 - 重新排列数组

我有一个数组，其中三个语义元素（a，b，c）以以下形式存储：

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

这意味着 ab 和 c 不是实际值。第一个 a 可能是 10，第二个是 1，第三个是 25，依此类推。ab 和 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]

4

1 回答 1

0

有一个 O(n.lgn) 时间分治算法，额外的内存使用量为 O(1)：

假设您要重新排序 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] in O(n) in-place with swap 操作。

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

于 2012-11-30T15:45:16.163 回答