可能重复：
矩阵的就地转置
最近参加了一次技术书面面试。通过以下问题。
我有一个数组说
testArray = {a1,a2,a3,...an,b1,b2,b3,....bn,c1,c2,c3,.....,cn}
我需要将此数组排序为`
testArray = {a1,b1,c1,a2,b2,c2,a3,b3,c3,.....,an,bn,cn}
约束是我不应该使用额外的内存，不应该使用任何内置函数。应该写完整的代码，可以是任何语言，也可以使用任何数据结构。
例如：
Input: {1,2,3,4,5,6,7,8,9}, n = 3
Output: {1,4,7,2,5,8,3,6,9}
我无法在约束范围内得到任何解决方案，任何人都可以提供解决方案或建议吗？
这只是一个矩阵转置操作。维基百科上甚至还有一个就地矩阵转置的问题和解决方案。
没有多余的空间是不可能的，因为您至少需要遍历数组。O(1)额外的内存是可能的，但会严重影响时间复杂度。
该解决方案基于维基百科页面中的循环算法：对于每个单元格，我们将找到循环中索引最小的单元格。如果索引最小的单元格大于或等于（>=）当前单元格的索引，我们将执行链交换。否则，我们忽略该单元格，因为它已正确交换。时间复杂度的（粗略分析的）上限可以高达 O((MN) 2 )（我们经过 M * N 个单元，并且周期只能与单元的总数一样长）。
如果不额外使用内存和任意长度，就不可能实现此算法，因为您需要一个迭代器来遍历列表并且占用空间。
对于数组的固定长度和固定n，您可以使用矩阵转置算法。并且为了交换元素 y
您正在寻找的算法是矩阵转置算法。因此，您必须在迭代每个元素时准确地交换它。
http://en.wikipedia.org/wiki/Transpose
基本上，您必须将第n个组件中的第m 个元素与第 m个组件中的第n个元素交换。这可以通过双循环来完成。
m = length(array)/n;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
{
index_1 = i * m + j;
index_2 = j * m + i
swap(index_1, index_2);
}
注意：对于固定的m和n ，这个循环可以完全展开，因此m, i, j可以用一个常数代替。
为了在不使用额外空间的情况下交换每个元素，您可以使用注释中指出的 XOR 交换算法：
X := X XOR Y
Y := Y XOR X
X := X XOR Y
在不使用临时变量的情况下交换两个数字（a 和 b）的最简单方法如下：
b = b + a;
a = b - a;
b = b - a;
如果你把它写在一个函数中，那么你就是其中的一部分。您如何在不使用临时变量的情况下跟踪要在数组中交换的变量，现在让我难以理解。
请记住选民：他实际上不需要对数组进行排序，只需交换正确的值。
编辑：这将适用于 Java 中的大值（以及 C/C++ 中，除非您打开一些非常激进的编译器优化 - 行为未定义但默认为 sane）。这些值只会环绕。
第二次编辑 - 一些（相当未经测试的）代码来翻转数组，我认为超过内存限制的 4 个整数。虽然从技术上讲它是非线程安全的，但它是可并行的，因为您最多只能访问每个数组位置一次：
static int[] a = {1,2,3,4,
5,6,7,8,
9,10,11,12,
13,14,15,16};
static int n = 4;
public static void main(String[] args)
{
for(int i = 0; i < a.length/n; i++) // 1 integer
for(int j = 0; j < n; j++) // 1 integer
if(j > i)
swap(i*n+j, j*n+i);
}
static void swap(int aPos, int bPos) // 2 integers
{
if(a[aPos] != a[bPos])
{
a[bPos] = a[aPos] + a[bPos];
a[aPos] = a[bPos] - a[aPos];
a[bPos] = a[bPos] - a[aPos];
}
}
如果这误解了这个问题，我们深表歉意；我仔细阅读了它，无法弄清楚除此之外还需要什么。