C++如何实现高效的数组元素原位循环移动 : 避免占用额外辅助内存开销

作者：袖梨 2026-07-27

不能直接用 std::rotate 是因为自定义类型可能不满足可移动/可复制要求，或某些 STL 实现未优化为环形置换；此时需手写环形置换法，用 gcd(n,k) 确定循环组数，仅靠三个指针和一个临时变量完成原位旋转。

为什么不能直接用 `std::rotate` 就完事？

多数人第一反应是调用 std::rotate —— 它确实原位、标准、简洁。但实际项目中常遇到两种情况让它失效：自定义类型不满足可移动/可复制要求（比如含非 trivial 析构或禁用拷贝的类），或者编译器对 std::rotate 的实现未做优化（某些嵌入式 STL 版本仍用三段拷贝而非环形置换）。此时必须手写逻辑，且不能依赖 std::move 或临时对象。

环形置换法：三个指针搞定任意步长移动

核心思路是把数组看作若干不相交的循环链，每个元素按步长 k 跳转，直到回到起点。关键在于计算循环节个数：gcd(n, k)，它决定了要启动几个独立循环。每轮循环内只用一个临时变量暂存值，其余靠赋值链完成。

实操要点：

先对 k 取模：k = k % n，避免无效整圈移动
用 std::gcd（C++17+）或手写欧几里得算法求循环组数
外层循环执行 gcd(n,k) 次，每次从索引 i 开始；内层循环直到回到 i
注意边界：当 n == 0 或 k == 0 直接返回，避免除零或空操作

示例（右移 2 位）：

立即学习“C++免费学习笔记（深入）”；

void rotate_right(int* arr, int n, int k) {    if (n <= 1 || k == 0) return;    k = k % n;    int cycles = std::gcd(n, k);    for (int i = 0; i < cycles; ++i) {        int temp = arr[i];        int j = i;        do {            int next = (j + k) % n;            std::swap(arr[j], arr[next]); // 或直接赋值：arr[j] = arr[next]            j = next;        } while (j != i);        arr[i] = temp; // 补回起点    }}

反转三次法：更易写对、且对缓存友好

比环形置换更少出错，原理简单：右移 k 等价于「整体反转 → 前 k 反转 → 后 n-k 反转」。所有操作都是对半交换，无取模、无循环计数，CPU 预取友好，尤其适合大数组。

使用场景与细节：

适用于任意整型、POD 类型；若类型含构造/析构，需确保 swap 是 noexcept 且廉价
k 必须先规约：k = k % n，否则反转区间越界
三次反转总交换次数恒为 n/2，而环形置换最坏也是 n 次赋值，性能接近
代码更短，边界处理直观（比如 reverse(arr, arr + k) 不会越界只要 k ）

简明实现：

void rotate_right(int* arr, int n, int k) {    if (n <= 1 || k == 0) return;    k = k % n;    std::reverse(arr, arr + n);    std::reverse(arr, arr + k);    std::reverse(arr + k, arr + n);}