将所有奇数定位元素移动到左半部分，并将偶数定位到右半部分原地 [英] Move all odd positioned element to left half and even positioned to right half in-place

问题描述

给定一个包含正整数和负整数的数组，将所有奇数索引元素向左移动，将所有偶数索引元素向右移动.

Given an array with positive and negative integers, move all the odd indexed elements to the left and even indexed elements to the right.

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

The difficult part of the problem is to do it in-place while maintaining the order.

例如

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

输出应该是:

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

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

If the order didn't matter, we could have been used partition() algorithm of quick sort.

如何在 O(N) 中做到这一点?

How to do it in O( N )?

推荐答案

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

1. Get largest sub-array having size 3^k+1
2. 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 (even-indexed elements to the left of sub-array, odd-indexed - to the right), the replaced element should be also moved to its proper position, etc. until this procedure comes back to the starting position. This paper gives number-theoretic explanation why such selection of starting positions shuffles sub-array to the correct order.
3. Process the remaining parts of the array recursively, using steps 1 and 2.
4. Now we only need to join the reordered parts together. Start with the smaller sub-arrays at the end of the whole array. To exchange sub-array halves, use reverse algorithm: reverse(reverse(a), reverse(b)); or, for sub-array halves of equal size, use pair-wise swaps.
5. Now all even-positioned elements are on the left. To get them on the right, as required, exchange elements i and i+N/2 for all i = 0 .. N/2-1.

算法就位，时间复杂度为 O(N).

Algorithm is in-place, time complexity is 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:

Variation of this algorithm, that does not need step 5:

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

• On step 1, get largest sub-array having size 3^k-1.
• On step 2, move even-indexed elements to the right of sub-array, odd-indexed - to the left. Use starting positions 0, 2, 8, ... 3^k-1-1 for cycle-leader algorithm.

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

Here is different O(N log N) in-place algorithm, which does not need number-theoretic proofs:

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)

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

This problem is just a special case of the In-place matrix transposition.

这篇关于将所有奇数定位元素移动到左半部分，并将偶数定位到右半部分原地的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！