C++如何实现数组的原位交换旋转 (避免占用额外空间)

先聊一个问题：面试里常遇到的“把数组向右循环移动k位，不许用额外数组”，到底该怎么写？很多人第一反应是std::rotate，但标准库的那个接口语义是左移，而且要求middle在区间内，直接用容易掉坑。更核心的是，如果你在嵌入式环境或者自定义容器里需要亲手控制每一步，就得理解原位旋转的底层机制——别只靠库函数糊弄过去。

这篇文章就拆两个最主流的原位方案：三次反转法和环状替换法。先给结论：日常写代码无脑选三次反转，只有特殊场景才考虑环状替换。

三次反转法：最可靠且易验证的原位方案

原理其实一句话就说完了：先把整个数组反转，再分别反转前k个元素和后n-k个元素，结果就是向右旋转k位。这不是什么黑科技，它本质上利用了反转操作的可组合性——数学上可以严格证明。时间复杂度O(n)，交换次数不超过n，而且对CPU缓存特别友好，因为访问模式是顺序的。

写的时候有几点容易忽略：

• k一定要先对n取模，否则索引越界；
• 反转函数最好用左闭右开区间，比如reverse(arr, 0, n)表示[0,n)，这样不容易出off-by-one；
• 如果传入的是std::vector，记得传引用或指针，别不小心拷贝了一份。

一段能跑的代码大概长这样：

void reverse(int* arr, int left, int right) {    while (left < right) {        std::swap(arr[left++], arr[--right]);    }}void rotate(int* arr, int n, int k) {    if (n == 0) return;    k = k % n;    reverse(arr, 0, n);    reverse(arr, 0, k);    reverse(arr, k, n);}

环状替换法：空间更省但边界条件多

另一个思路是环状替换——从下标0出发，每次跳k步把元素搬到新位置，直到转回起点，这就算一轮；一共需要gcd(n,k)轮。它的交换次数就是n，而且只用一个临时变量，内存占用理论上是零额外。但代价是代码逻辑绕，很容易踩坑：

• 轮数必须是gcd(n,k)，不是k也不是n/k；
• 内层循环的终止条件如果用next != start，别忘了在循环体内更新next，否则死循环伺候；
• 搬运过程中要先把起点元素存起来，不然会被覆盖；
• (i + k) % n这个计算，如果k和n都是int，大数时可能溢出，最好转成size_t。

什么时候该选哪种方法？

现实项目中，三次反转法几乎总是更优的选择——代码一目了然，调试时出问题一眼就能看出来，而且对cache友好。环状替换法真正的应用场景只有两个：一是题目明确要求“只能用常数额外空间”且“交换次数要最小”，二是你在写硬件寄存器映射数组，连栈上临时变量都得省着用——但这种场景极其少见。

最后补充一个容易被忽略的细节：k为负数时怎么办？C++标准里%对负整数的结果是实现定义的，不同编译器可能给出不同符号。保险的做法是显式归一化：k = ((k % n) + n) % n。另外n == 0时的边界也必须处理，否则任何操作都会引发未定义行为。