a1 b1 a2 b2 ... an bn
操作后，它变成了
a1 a2 a3 ... an b1 b2 ... bn
这是可能的，但是非常复杂！更简单的O（nlogn）和O（1）空间解决方案在编写代码和缓存方面可能更好。
我们将解决一个与你的问题不同的问题，但是一旦我们解决了那个问题，你的问题就变得微不足道了。
考虑数组为
b1, a1, b2, a2, ..., bn, an
你需要将这个转换为
a1, a2, ..., an, b1, b2, ..., bn
与1到2n的索引一起工作，我们可以看到这是由以下内容给出的：
i -> (n+1)*i (mod 2n+1).
一种O(nlogn)时间复杂度且O(1)空间复杂度的解决方案
我们可以采用分治法来解决问题。
首先，对于接近n/2的m值，将数组
b1, a1, ..., bn , an
转换为
a1,a2,...am, b1,b2, ..bm, a(m+1), ..., an, b(m+1), ... , bn
通过递归地应用于前2m个元素，然后是剩余的元素。
现在我们只需要将中间数组循环移位m个位置（这可以在O(n)时间和O(1)空间内完成）
得到
a1, a2, .., am , a(m+1), ..., an, b1, b2, ..., bm, b(m+1), ..., bn.
b1 a1, b2 a2, .. bm am, b(m+1) a(m+1), ..., bn an
b1 a1, b2 a2, .. bm am, a(m+1) b(m+1), ..., an bn
b1，b2，..，bm，a（m + 1），a（m + 2）...，a（n）。a(m+1) a1, a(m+2) a2, ..., a(2m) am, a(2m+1) b(m+1),...,an b(n-m), b1 b(n-m+1),...,bm bn
a(m+1) a1, a(m+2) a2, ..., a(2m) am, b(m+1) a(2m+1),...,b(n-m) an,b(n-m+1) b1,..., bn bm
[a1 a2 ... am][a(m+1) ... a(2m)] [a(2m+1) ...an b1 b2 .. bm][b(m+1) ... bn]
无论2m>=n还是不成立，此方法都可行。
因此，这是一个O(nlogn)时间复杂度和O(1)空间复杂度的算法。
一个O(n)时间复杂度和O(1)空间复杂度的解决方案。
所使用的思路类似于以下论文中使用的思路：Inshuffle的简单原地算法。
您需要阅读该论文以了解下面的内容。我建议您还应阅读：如何掌握原地数组修改算法？
这基本上是在上述论文中解决的问题的反向置换。
当2n+1为3的幂（记为3^m）时，解决此问题就足够了，因为之后可以使用分治（就像O(nlogn)的解决方案一样）。
现在2n+1和n+1互质，因此在模3^m的情况下，我们可以看到n+1必须是2的某个幂次方。（再次参见那篇论文，以了解为什么：基本上，与3^m互质的任何数在模3^m下都是2的幂次方）。
假设n+1=2^k（我们还不知道k，并且请注意这是模3^m的情况）。
找到k的方法是计算n+1的幂，直到它变为1。这给了我们k（最多需要O(n)时间）。
现在我们可以看到排列的循环（请参见上述论文/stackoverflow链接）从以下位置开始：
2^a*3^b
其中0 <= a < k，0 <= b < m。
因此，您从每个可能的(a,b)对开始，并跟随置换的循环，这将给出一个时间复杂度为O(n)，原地算法，因为您不会超过一定数量的次数触摸每个元素！
这有点简短（！），如果您需要更多信息，请告诉我。
好的，让我来解释一下。请尝试以下代码：
i = 0 /* linear array index */
do j = 1 to c /* j = 1 to virtural columns */
do k = 1 to r /* k = 1 to virtural rows */
i = i + 1
sp = (k - 1) * c + j
do while sp < i
ct = (sp - 1) % r + 1
rt = sp - (ct - 1) * r
sp = (rt - 1) * c + ct
end
if i \= sp then say 'swap('i',' sp')' /* swap elements */
end
end
A1, B1, A2, B2, A3, B3, A4, B4
swap(2, 3)
swap(3, 5)
swap(4, 7)
swap(6, 7)
变成：
A1, A2, A3, A4, B1, B2, B3, B4
DO WHILE循环。对于给定数量的行，需要多少次迭代？答案可能是：相当多。基于一些经验结果（如下所示），看起来DO WHILE迭代次数是一个涉及'r'的复杂函数，当'c'=2时（或者可能是任何值'c'）。我没有足够的O-foo来确定这个函数是什么。然而，它不应该比N3更糟糕（一次完整的矩阵“追逐”，N2次每个元素，N）。从理论上讲，这不是一个好的情况。所以我猜这使得它成为O(N3)？这可能是一个非O(N)算法，但在实际情况下，根据下面的经验数据，它似乎表现接近O(N)。我有点迷失了 - 欢迎评论！
关于DO WHILE循环的一个观察：它使用简单变量的整数基础数学（不需要数组引用）。如果你要进行非线性运算，这肯定是最便宜的地方！
需要多少次交换？每次迭代通过外部两个循环的交换次数限制为一次，最多N次。交换次数符合O(N)性能。
我猜这不是一个O(N)算法，但对于中等大小的2列矩阵似乎具有合理的行为。
以下是各种2列矩阵尺寸的经验结果：
Rows Loops per row
========== =============
500 9
1,000 19
1,500 21
2,000 12
2,500 18
3,000 23
3,500 26
1,000,000 30
2,000,000 40
3,000,000 45
10,000,000 59
20,000,000 39
30,000,000 60
11, 12, 13, ... 1N, 21, 22, 23, ... 2N, ... M1, M2, M3 ... MN
描述线性数组中每个元素的符号为：
X[i,r,c]
其中：i是元素X在线性数组中的索引
r是元素X的行编号
c是元素X的列编号。
使用此符号，可以按行主序生成一个数组：
i = 0
for j = 1 to M /* Row counter */
for k = 1 to N /* Column counter */
i = i + 1 /* array index of element j, k */
say 'X['i','j',k']'
end
end
i = (j - 1) * N + k
矩阵X的转置是通过在r和c范围内交换X [i，r，c]和X [t，c，r]元素构建的。本质上，我们交换所有行变量和列变量。使用上面描述的符号，这相当于交换线性数组元素：
exchange(X[i,r,c], X[t,c,r])
其中：i = (r - 1) * N + c t = (c - 1) * M + i
将矩阵转置所需的交换次数将小于M * N，因为最多只需要一个交换即可将元素放置到正确的位置。在某些情况下，不需要交换，因为该元素已经“就位”。例如，X的第一个和最后一个元素永远不需要交换。
通过按增加i的顺序遍历线性数组，我们知道只要没有任何交换涉及i> t的元素，对于所有索引小于或等于i的元素，矩阵将以列主顺序排列。
每当 i > t 时，这意味着在索引 t 处进行了先前的交换。 在上述指示下，t 处的元素被交换到某个新位置 t'。给定索引 t，我们可以计算行主索引 t' 以及与之关联的行和列号，如下所示： c' = (t - 1) % M + 1
r' = t - (c' - 1) * M
t' = (r' - 1) * N + c'
再次，如果t'小于i，则意味着此元素也已交换，我们必须继续进行另一轮计算。将t设置为计算出的t'并重复。最终，i将变成<= t，并且可以进行交换。基本上，我们通过所有先前的交换“追踪”元素，直到在线性数组中找到它在i处或i右侧。
对于线性数组中的每个元素重复此循环，矩阵将被转置。
好的，让我们看一个例子：
0 1 2 3 4 5 6 7 8 9 10
0 2 4 6 8 10 1 3 5 7 9
结果的前一半包含索引为原始索引 i 的 i / 2 元素，而另一半则是 i - n / 2 + 1，其中 n 是数组中的项目数。
这基本上是排序算法的一个特殊情况，只是设置了一个特殊的顺序。
因此，这里有一个使用冒泡排序算法对整数数组进行排序的想法。我们需要将偶数值移到前面，留下奇数值：
0 1 2 3 4 5 6 7 8 9 10
* *
0 2 1 3 4 5 6 7 8 9 10
* *
0 2 1 4 3 5 6 7 8 9 10
* *
0 2 4 1 3 5 6 7 8 9 10
* *
0 2 4 1 3 6 5 7 8 9 10
* *
...
0 2 4 6 1 3 5 7 8 9 10
* *
...
0 2 4 6 8 1 3 5 7 9 10
* *
只有在保留索引的情况下才能正常工作（即在此情况下，索引与数组值相关）。而冒泡排序的性能为O(n^2)，内存使用量为1。
如果仅使用通用排序算法，则无法在O(n)时间和1内存中完成[编辑：]，最好的通用排序算法的执行时间为O(nlog n)：
http://en.wikipedia.org/wiki/Sorting_algorithm
为了解决您的问题，最好的方法是生成一个符合您条件的索引数组：size_t* indices = new size_t[n];
// n is the number of items in the original array
for (int i = 0; i < n; i++)
{
if (i < n / 2)
{
indices[i] = i * 2;
}
else
{
indices[i] = i - n / 2 + 1;
}
}
然后简单地使用它将原始数组中的项目映射到新位置：
// i is the new index here, which makes it appear as if ValuesArray has been sorted
Type* getOddEvenValue(size_t newIndex)
{
// ValuesArray and indices should be available in this scope, of course
return ValuesArray[indices[newIndex]];
}
这个东西可以在O(n)的时间内运行，但也需要O(n)的内存。但如果Type的大小比int的大小大得多，那么它仍然可以节省内存使用量（而不是复制Type对象）。
[编辑2:]
与优美的面向对象编码和andand did相反，后者还要求您将原始向量复制到类的实例中，您可以简单地编写一个函数：
size_t permuted_index(size_t i, size_t vecSize)
{
return ( i < vecSize/2 ? i * 2 : 2 * (i - vecSize/2) + 1);
}
每当您需要获取排列值时，请使用它。实际上，这只需要O(n)的时间，因为对于给定的向量，permutted_index最多只会被评估n次（在完整的“for each”循环中至少如此）。
O(1) 时间，O(1) 额外空间
#include <vector>
#include <iostream>
#include <ctime>
#include <boost/random.hpp>
template <typename T>
class pvec
{
private:
// Stores values to permute
std::vector<T> v;
// Flag; true when permuted; false when not
bool permuted;
public:
pvec(size_t size) : v(size), permuted(false) {}
// Set the permutation flag
void set_p(bool p) { permuted = p; }
// When the permuted flag is set, return the permuted element, otherwise
// return the non-permuted element
T& operator[](size_t i) { return (permuted ? v[p_ind(i)] : v[i]); }
// Pass through the size of the vector used
size_t size() const { return v.size(); }
private:
// Used to determine the permuted index of a given index
size_t p_ind(size_t i) const
{
return ( i < v.size()/2 ? i * 2 : 2 * (i - v.size()/2) + 1);
}
};
// Used to display a pvec instance
template <typename T>
std::ostream& operator<<(std::ostream& os, pvec<T>& v)
{
for (size_t i = 0; i < v.size(); ++i)
os << (i == 0 ? "<" : ", ") << i << ":" << v[i];
os << ">";
return os;
}
int main(int argc, char** argv)
{
const size_t size = 8;
pvec<uint32_t> v(size); // Array containing test values
// Boost Random Number Library used to generate random values in the test
// array
boost::mt19937 rng(std::time(0));
boost::uniform_int<> dist(0,65536);
boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
var(rng, dist);
// Generate random test values
for (size_t i = 0; i < size; ++i)
v[i] = var();
// Observer original vector
std::cout << v << std::endl;
// Set the permutation flag O(1) time
v.set_p(true);
// Observe the permuted vector
std::cout << v << std::endl;
return 0;
}输出:
<0:44961, 1:246, 2:54618, 3:41468, 4:12646, 5:21691, 6:26697, 7:36409> <0:44961, 1:54618, 2:12646, 3:26697, 4:246, 5:41468, 6:21691, 7:36409>
O(1)，因为打印答案本身就是O(n)的。此外，问题明确要求以某种方式移动元素，而不仅仅是打印它们。另外，使用混杂了boost和复杂类的C++来回答算法问题并不是个好主意。伪代码或易于理解的C++会更有帮助。-1。 - IVlad