c++ - 从右侧移动到奇数位置，从左侧移动到偶数位置

Question

给定一个非空的项目数组。您必须将所有项目从右侧移动到奇数位置(从零开始)，并从左侧移动到偶数位置，如下所示:

原始数据: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

对于这个具有 O(n) 时间复杂度的就地算法存在什么？它的实现是什么？

逆问题解决了here (这个算法本质上是可以倒过来的，但是会很难看)。

Answer 1

这里只是算法本身。有关详细信息、解释和替代方法，请参阅 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 递归处理数组的剩余部分。

这个问题比OP中提到的逆问题更简单，因为这里我们必须从大的开始重新排序子数组，按照与循环领导者算法相同的顺序(逆问题必须单独做并且倒序，从小的开始，复杂度为O(N))。