数组的旋转与移位：左旋、右旋与循环移位算法

数组的旋转与移位，说白了就是让数组里的元素「转起来」。

我刚开始学C语言时，觉得这玩意儿不就是把元素挪个位置吗？后来在项目中做数据缓冲区管理，才发现这玩意儿坑不少。你想想看，一个环形队列、一个滚动显示、甚至某些加密算法，底层都离不开数组移位。

今天咱们就把左旋、右旋、循环移位这几个东西彻底讲透。

什么是数组旋转？

先给个直观感受。

假设你有一个数组：[1, 2, 3, 4, 5]

• 左旋1位：把第一个元素移到末尾 → [2, 3, 4, 5, 1]
• 右旋1位：把最后一个元素移到开头 → [5, 1, 2, 3, 4]

嗯，就这么简单。但实际写代码时，要考虑效率、边界条件、以及——别把数据搞丢了。

左旋算法

左旋k位，就是把数组前k个元素「切下来」放到末尾。

我习惯用三种方式实现，每种都有它的适用场景。

方法一：暴力移位法

最直接的想法——一次移一位，重复k次。

void leftRotateByOne(int arr[], int n) {
    int temp = arr[0];
    for (int i = 0; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    arr[n - 1] = temp;
}

void leftRotate(int arr[], int n, int k) {
    k = k % n;  // 防止k大于n
    for (int i = 0; i < k; i++) {
        leftRotateByOne(arr, n);
    }
}

这个方法好理解，但效率低。时间复杂度O(n*k)，n大了就扛不住。我在做嵌入式项目时用过一次，数组只有几十个元素，倒也没啥问题。但如果你处理的是上万个元素，千万别这么干。

方法二：临时数组法

开一个临时数组，把前k个元素存起来，剩下的往前挪，再把临时数组的内容放回末尾。

void leftRotate(int arr[], int n, int k) {
    k = k % n;
    int temp[k];
    
    // 1. 保存前k个元素
    for (int i = 0; i < k; i++) {
        temp[i] = arr[i];
    }
    
    // 2. 剩余元素左移
    for (int i = k; i < n; i++) {
        arr[i - k] = arr[i];
    }
    
    // 3. 把temp放回末尾
    for (int i = 0; i < k; i++) {
        arr[n - k + i] = temp[i];
    }
}

时间复杂度O(n)，空间复杂度O(k)。

这里有个坑——C语言里变长数组（VLA）在有些编译器上不支持。我建议你直接用动态内存分配，或者把k设成固定大小。

方法三：反转法（最优雅）

这个方法我第一次看到时，觉得太巧妙了。它基于一个数学观察：

左旋k位 = 反转前k个 + 反转后n-k个 + 反转整个数组

void reverse(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

void leftRotate(int arr[], int n, int k) {
    k = k % n;
    reverse(arr, 0, k - 1);      // 反转前k个
    reverse(arr, k, n - 1);      // 反转后n-k个
    reverse(arr, 0, n - 1);      // 反转整个数组
}

时间复杂度O(n)，空间复杂度O(1)。

我曾经在面试中被问到这道题，当时我写了暴力法，面试官笑了笑说「还有更好的吗？」——嗯，从那以后我就把反转法刻在脑子里了。

右旋算法

右旋和左旋本质上是一回事。右旋k位，相当于左旋n-k位。

所以你可以直接复用左旋的代码：

void rightRotate(int arr[], int n, int k) {
    k = k % n;
    leftRotate(arr, n, n - k);  // 右旋k = 左旋n-k
}

当然，你也可以用反转法直接实现右旋：

void rightRotate(int arr[], int n, int k) {
    k = k % n;
    reverse(arr, 0, n - 1);      // 反转整个数组
    reverse(arr, 0, k - 1);      // 反转前k个
    reverse(arr, k, n - 1);      // 反转后n-k个
}

你看，反转的顺序变了。左旋是先局部再整体，右旋是先整体再局部。这个细节容易搞混，我建议你画个图记一下。

循环移位算法

循环移位和旋转其实是一回事，只是叫法不同。但有一种特殊情况值得单独拿出来讲——原地循环移位，也就是不开额外数组，只用O(1)额外空间。

反转法就是典型的原地循环移位。除此之外，还有一种「环状替换法」，它像多米诺骨牌一样，一个元素把另一个元素挤走，被挤走的再去挤下一个，直到回到起点。

void leftRotateCycle(int arr[], int n, int k) {
    k = k % n;
    int moved = 0;  // 已经移动的元素个数
    
    for (int start = 0; moved < n; start++) {
        int current = start;
        int prev = arr[start];
        
        do {
            int next = (current + k) % n;
            int temp = arr[next];
            arr[next] = prev;
            prev = temp;
            current = next;
            moved++;
        } while (start != current);
    }
}

这个方法的时间复杂度也是O(n)，空间O(1)。但代码逻辑稍微绕一点，我一般只在面试时秀一下，实际项目中还是用反转法，因为可读性更好。

三种方法对比

方法	时间复杂度	空间复杂度	适用场景
暴力移位法	O(n*k)	O(1)	n很小，k也很小
临时数组法	O(n)	O(k)	k不大，且允许额外空间
反转法	O(n)	O(1)	通用，推荐首选
环状替换法	O(n)	O(1)	追求极致空间效率

避坑指南

我这些年写数组移位踩过的坑，给你列几个：

• k可能大于n：一定要取模，否则数组越界。我曾经在代码里忘了这茬，结果调试了一下午。
• k为负数：有些场景下k可能是负数，表示反向旋转。处理方式：k = (k % n + n) % n。
• n为0或1：边界情况，旋转没有意义，直接返回。
• 数组类型：上面的例子都是int数组，但原理适用于任何类型。如果你写通用函数，可以用void* + memcpy。

知识体系总览

下面这张图把数组旋转与移位的核心逻辑串起来了，你可以对照着看。

总结

数组旋转与移位，说白了就是「分段交换」四个字。

我个人最推荐反转法，代码简洁、效率高、不容易出错。如果你在面试中遇到这道题，直接写反转法，面试官一般都会点头。

嗯，今天就到这里。代码多敲几遍，自然就熟了。

---