从右侧移动到奇数位置，并从左侧即使就地 [英] move from right side to odd positions and from left side to even in-place

问题描述

鉴于项的非空数组。你必须移动从右侧的所有项目，以奇位置（从零开始），并从左侧 - 甚至位置，如下所示：

Given a non-empty array of items. You have to move all the items from the right side to odd positions (zero-based), and from the left side — to even positions, as follows:

原始数据：0 2 4 6 8 10 12 14 1 3 5 7 9 11 13

raw data: 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13

结果：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

result: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

什么就地这个算法存在着O（n）的时间复杂度？什么是它的实现？

What in-place algorithm exists for this with O(n) time complexity? What is its implementation?

逆问题就解决了​​<一href="http://stackoverflow.com/questions/12338654/move-all-odd-positioned-element-to-left-half-and-even-positioned-to-right-half-i"标题=点击这里>这里（该算法可基本反转，但它看起来会比较难看）。

The inverse problem is solved here (this algorithm can be essentially inverted, but it will look ugly).

推荐答案

在这里仅仅是算法本身。有关详细信息，解释和替代方法请参阅该反问题 答案。

Here is only the algorithm itself. For details, explanations, and alternative approaches see answer for the inverse problem.

1. 初始化指针右侧元素为N / 2的游泳池。
2. 在获取最大的有子数组大小3 ^K +1
3. 加入（3 ^K +1）从数组的开始/ 2单元和（3 ^K +1）从右侧的元素在泳池边/ 2个元素交换适当子阵列。更新池指针。
4. 在应用周期的领导者算法来此子阵列的部分，从位置1，3，9起，... 3 ^K-1 ：移动元素到适当的位置，子阵（从子阵，甚至位置，从右边的左边元素 - 奇位置），替换元素也应转移到适当的位置，等等，直到此过程又回到起始位置
5. 处理数组递归的其余部分，使用步骤2。4。

1. Initialize pointer to the pool of right-side elements to N/2.
2. Get largest sub-array having size 3^k+1
3. Join (3^k+1)/2 elements from the array's beginning and (3^k+1)/2 elements from the pool of right-side elements by exchanging appropriate sub-arrays. Update pool pointer.
4. Apply cycle leader algorithm to the parts of this sub-array, starting from positions 1, 3, 9, ... 3^k-1: move element to its proper position in sub-array (elements from the left of sub-array to even positions, from the right - to odd positions), the replaced element should be also moved to its proper position, etc. until this procedure comes back to the starting position.
5. Process the remaining parts of the array recursively, using steps 2 .. 4.

此问题比逆问题，在OP所指更简单，因为在这里我们必须重新排序的子阵列从较大的起始，在相同的顺序操作的周期领袖算法（逆问题必须单独做，并以相反的顺序，从较小的开始​​得到O（N）的复杂性）。

This problem is simpler than the inverse problem, referred in OP, because here we have to reorder sub-arrays starting from the larger ones, in the same order as doing cycle leader algorithm (the inverse problem has to do it separately and in reverse order, starting from the smaller ones to obtain O(N) complexity).

这篇关于从右侧移动到奇数位置，并从左侧即使就地的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！