将所有奇数定位元素移动到左半边,甚至定位到右半边

Question

给定一个具有正整数和负整数的数组,将所有奇数索引元素移动到左侧,甚至将索引元素移动到右侧.

问题的难点在于在维持秩序的同时就地完成.

例如

7, 5, 6, 3, 8, 4, 2, 1

输出应该是:

5, 3, 4, 1, 7, 6, 8, 2

如果顺序无关紧要,我们可以使用快速排序的partition()算法.

如何在O(N)中完成？

Answer 1

1. 获得大小为3 ^k +1的最大子阵列
2. 将循环引导算法应用于该子阵列的各个部分,从位置1,3,9开始... 3 ^k-1:将元素移动到子数组中的正确位置(子数组左侧的偶数索引元素) -array,odd-indexed - to right),被替换的元素也应该移动到正确的位置等,直到这个过程回到起始位置.本文给出了数论解释为什么这种起始位置的选择将子阵列改组为正确的顺序.
3. 使用步骤1和2递归处理数组的其余部分.
4. 现在我们只需要将重新排序的部分加在一起.从整个数组末尾的较小子数组开始.要交换子阵列的一半,使用反向算法:反向(反向(a),反向(b)); 或者,对于相同大小的子阵列,使用成对交换.
5. 现在所有偶数位置元素都在左侧.为了使它们在右边,根据需要,为所有i = 0 ... N/2-1交换元素i和i + N/2.

算法就地,时间复杂度为O(N).

例:

0 1 2 3 4  5 6 7 8 9   10 11 (the original array)
0 1 2 3 4  5 6 7 8 9 # 10 11 (split to sub-arrays)
0 2 4 3 8  1 6 5 7 9 # 10 11 (first cycle leader iteration, starting with 1)
0 2 4 6 8  1 3 5 7 9 # 10 11 (second cycle leader iteration, starting with 3)
0 2 4 6 8  9 7 5 3 1 # 10 11(2nd half of 1st part& 1st half of 2nd part reversed)
0 2 4 6 8 10 1 3 5 7    9 11 (both halves reversed together)

这个算法的变化,不需要第5步:

• 在步骤1中,获得大小为3 ^k -1的最大子阵列.
• 在步骤2中,将偶数索引元素移动到子数组的右侧,奇数索引 - 向左移动.使用起始位置0,2,8,... 3 ^k-1 -1作为循环前导算法.

这是不同的O(N log N)就地算法,它不需要数论证明:

1. 将数组重新解释为一系列单元素2*2矩阵,转置这些矩阵.
2. 将结果重新解释为一系列双元素2*2矩阵并转置它们.
3. 矩阵大小小于数组大小时继续.
4. 现在我们只需要将重新排序的部分连接在一起(与之前的算法完全相同).
5. 交换阵列左右两半的元素(与以前的算法完全相同).

例:

0  1   2 3   4 5   6 7  (the original array)
[0 2] [1 3] [4 6] [5 7] (first transposition)
[0 2] [4 6] [1 3] [5 7] (second transposition)

这个问题只是就地矩阵转置的一个特例.