performance - 将所有奇数定位的元素原地移动到左半部分，偶数定位到右半部分

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 开始:将元素移动到子数组中的适当位置(子数组左边的偶数索引元素，右边的奇数索引元素)，被替换的元素也应该移动到它的正确位置，等等，直到这个过程回到起始位置。 This paper给出数论解释为什么这样选择起始位置会将子数组改组到正确的顺序。
3. 使用步骤 1 和 2 递归处理数组的剩余部分。
4. 现在我们只需要将重新排序的部分连接在一起。从整个数组末尾的较小子数组开始。要交换子数组的一半，请使用反向算法:reverse(reverse(a), reverse(b));或者，对于大小相等的子数组，使用成对交换。
5. 现在所有偶数位置的元素都在左边。为了让它们在右边，根据需要，将元素 i 和 i+N/2 交换为所有 i = 0 .. N/2-1。

算法就地，时间复杂度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)

这个问题只是In-place matrix transposition的一个特例.