给定一个大小为3n的形式的数组
[x1, x2, x3... xn, y1, y2, y3... yn, z1, z2, z3... zn]
转换成 [x1, y1, z1, x2, y2, z2, ... xn, yn, zn]
[x1, y1, z1, x2, y2, z2, ... xn, yn, zn]
xn，yn，zn可以是任何整数。请参见下面的示例输入和输出。
两个约束
输入和输出示例如下。
输入： [5, 8, 11, 3, 2, 17, 21, 1, 9] 3n =9。因此n = 3。
[5, 8, 11, 3, 2, 17, 21, 1, 9]
这里 x1=5 x2=8 x3=11 y1=3 y2=2 y3=17 z1=21 z2=1 z3=9
x1=5 x2=8 x3=11 y1=3 y2=2 y3=17 z1=21 z2=1 z3=9
输出： [5, 3, 21, 8, 2, 1, 11, 17, 9]
[5, 3, 21, 8, 2, 1, 11, 17, 9]
一种可能的O（n log n）解决方案： 仅考虑x和y。现在，我可以将所有y交换到其位置，这将使x2，x4，x6交换出位置。然后我将交换x2，x4，这将使x3，x7离开位置。下一个迭代将是x8，x16。这会将我带到O（n log n），而不是O（n）。
由于David似乎不希望将其写下来（很显然他 很 感兴趣，请参见其他答案:)，因此我将使用他的引用来得出针对具有3个分区的情况的算法。
首先请注意，如果我们可以使用算法 A在 m <n的范围内_有效解决问题，则可以重新排列数组，以便可以应用 _A ，然后剩下一个较小的子问题。说原来的数组是
x1 .. xm x{m+1}.. xn y1 .. ym y{m+1} .. yn z1 .. zm z{m+1} .. zn
我们想将其重新排列为
x1 .. xm y1 .. ym z1 .. zm x{m+1} .. xn y{m+1} .. yn z{m+1} .. zn
这基本上是图案的变换AaBbCc到ABCabc其中A，B，C和A，B，C具有相同的长度，分别。我们可以通过一系列逆转来实现。让X’在这里表示字符串X的反转：
AaBbCc
ABCabc
AaBbCc -> Aa(BbCc)' = Aac'C'b'B' -> Aac'(C'b')'B' = Aac'bCB' -> A(ac'bCB')' = ABC'b'ca' -> ABCb'ca' -> ABC(b'ca')' = ABCac'b -> ABCa(c'b)' = ABCab'c -> ABCabc
可能有更短的方法，但是这仍然是恒定数量的操作，因此只需要线性时间。在这里可以使用一种更复杂的算法来实现一些循环移位，但这只是一种优化。
现在我们可以递归地解决数组的两个分区了，我们就完成了。
问题仍然是，什么样的方法可以使我们轻松解决左侧问题？
为了弄清楚这一点，我们需要意识到我们要实现的是数组索引的特定排列 P。每个置换都可以分解为一组周期 a0 -> a1 -> ... -> a{k-1} -> a0，为此，我们有P（ai）= a {（i + 1）％k}。就地处理这种循环很容易，该算法已在Wikipedia上概述。
a0 -> a1 -> ... -> a{k-1} -> a0
现在的问题是，在完成一个循环的处理之后，要查找尚未处理的属于循环的元素。没有通用的解决方案，但是对于某些特定的排列，有很好的公式来描述不同循环中确切的位置。
对于您的问题，只需选择m =（5 ^（2k）-1）/ 3，这样m <n且k为最大值。属于所有不同循环的元素序列为5 ^ 0、5 ^ 1，…，5 ^ {k-1}。您可以使用它们在O（m）中的数组的左侧部分（移位后）实现循环前导算法。
我们递归地解决剩余的右边部分，并得到一种算法来及时解决问题
T(n) = O(m) + T(n - m)
并且由于m> = Omega（n），我们得到T（n）= O（n）。
