C++中如何实现数组移位？三种算法性能对比-C++-PHP中文网

C++中如何实现数组移位？三种算法性能对比

P粉602998670

发布： 2025-06-27 13:09:02

原创

438人浏览过

数组移位的最优方法是三次反转法。1.三次反转法通过将数组分为两部分分别反转后再整体反转，实现高效移位；2.其时间复杂度为o(n)，空间复杂度为o(1)，兼具时间与空间效率优势；3.在k大于数组长度时，通过对k取模避免冗余操作；4.实际项目中选择方法需权衡效率、可读性与维护性，三次反转法适用于对效率要求较高的场景。

C++中如何实现数组移位？三种算法性能对比

数组移位，说白了就是把数组中的元素整体向左或向右挪动位置。这事儿听起来简单，但不同的实现方法效率可是天差地别。最直接的方法可能效率最低，而稍微动点脑筋，就能让性能提升几个数量级。

解决方案：

实现C++数组移位，可以考虑以下三种主要算法：

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

直接移位法： 这是最直观的方法，每次将数组的所有元素向左或向右移动一位。如果需要移动k位，就重复这个过程k次。
辅助数组法： 创建一个辅助数组，将原数组中需要移动的元素复制到辅助数组的相应位置，然后将辅助数组的内容复制回原数组。
三次反转法： 将数组分为两个部分，分别进行反转，然后再对整个数组进行反转。例如，将数组向右移动k位，可以先反转前n-k个元素，再反转后k个元素，最后反转整个数组。

性能对比：

直接移位法： 时间复杂度为O(n*k)，其中n是数组的长度，k是移动的位数。空间复杂度为O(1)。这种方法效率最低，特别是当k接近n时。
辅助数组法： 时间复杂度为O(n)，空间复杂度为O(n)。虽然时间复杂度比直接移位法好，但需要额外的空间。
三次反转法： 时间复杂度为O(n)，空间复杂度为O(1)。这种方法既高效，又不需要额外的空间，通常是最佳选择。

为什么三次反转法如此高效？

三次反转法的巧妙之处在于，它将移位操作转化为一系列的反转操作，而反转操作可以在O(n)的时间复杂度内完成。例如，要将数组 [1, 2, 3, 4, 5] 向右移动2位，变成 [4, 5, 1, 2, 3]，可以这样做：

反转前n-k个元素：[1, 2, 3] 反转为 [3, 2, 1]，数组变为 [3, 2, 1, 4, 5]
反转后k个元素：[4, 5] 反转为 [5, 4]，数组变为 [3, 2, 1, 5, 4]
反转整个数组：[3, 2, 1, 5, 4] 反转为 [4, 5, 1, 2, 3]

可以看到，通过三次反转，就完成了数组的移位操作，而且整个过程只需要O(n)的时间复杂度。这种方法避免了直接移位法中大量的元素移动操作，因此效率更高。

如何处理移动位数k大于数组长度n的情况？

当移动位数k大于数组长度n时，直接对k取模，即 k = k % n。这样做是因为移动n位相当于没有移动，所以只需要考虑移动k模n位即可。

例如，如果数组长度为5，需要移动7位，那么实际上只需要移动2位。

#include <iostream>
#include <vector>
#include <algorithm>

void rotateArray(std::vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n; // 处理k大于n的情况

    std::reverse(arr.begin(), arr.begin() + n - k);
    std::reverse(arr.begin() + n - k, arr.end());
    std::reverse(arr.begin(), arr.end());
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    int k = 2;
    rotateArray(arr, k);

    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl; // 输出: 4 5 1 2 3

    return 0;
}

登录后复制