C++ 数组逆置实现详解及源码

对称位置元素交换

双指针思想

设置两个指针：

• left：指向数组开头
• right：指向数组末尾

不断交换，直到二者相遇。

时间与空间复杂度分析

• 时间复杂度：
  每个元素最多参与一次交换 → O(n)
• 空间复杂度：
  只使用常数个临时变量 → O(1)

实现思路

核心算法流程

left = 0 right = n - 1 while left < right: swap(arr[left], arr[right]) left++ right--

为什么循环条件是 left < right？

• 当 left == right：中间元素无需交换
• 当 left > right：已经完成逆置

swap 的本质

交换两个元素，本质是：

• 使用一个临时变量
• 或调用 std::swap

扩展到泛型的关键

• 使用模板
• 只要求类型支持拷贝 / 交换

完整实现代码

/************************************************************
 * 文件：ArrayReverse.h
 * 描述：数组逆置工具函数
 ************************************************************/
#ifndef ARRAY_REVERSE_H
#define ARRAY_REVERSE_H
#include <vector>
#include <cstddef>
#include <utility>

/**
 * @brief 逆置 C 风格数组（指针 + 长度）
 */
template<typename T>
void ReverseArray(T* arr, size_t length) {
    if (arr == nullptr || length == 0) return;
    size_t left = 0;
    size_t right = length - 1;
    while (left < right) {
        // 交换对称位置的两个元素
        std::swap(arr[left], arr[right]);
        ++left;
        --right;
    }
}

/**
 * @brief 逆置 std::vector
 */
template<typename T>
void ReverseArray(std::vector<T>& vec) {
    ReverseArray(vec.data(), vec.size());
}

#endif // ARRAY_REVERSE_H

/************************************************************
 * 文件：main.cpp
 * 描述：数组逆置测试示例
 ************************************************************/
#include <iostream>
#include "ArrayReverse.h"

int main() {
    // 示例 1：C 风格数组
    int arr[] = {1, 2, 3, 4, 5};
    size_t len = sizeof(arr) / sizeof(arr[0]);
    ReverseArray(arr, len);
    std::cout << "Reversed C array: ";
    for (size_t i = 0; i < len; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    // 示例 2：std::vector
    std::vector<int> vec = {10, 20, 30, 40};
    ReverseArray(vec);
    std::cout << "Reversed vector: ";
    for (int v : vec)
        std::cout << v << " ";
    std::cout << std::endl;

    return 0;
}

代码详细解读

ReverseArray(T* arr, size_t length)

作用：

• 对任意类型的一维数组进行原地逆置
• 使用双指针法
• 不依赖额外空间

ReverseArray(std::vector&)

作用：

• 为 STL 容器提供友好接口
• 内部复用指针版本实现
• 保证逻辑一致性

std::swap 的作用

作用：

• 交换两个对象
• 内部可针对类型进行优化
• 泛型算法首选

项目总结

本项目实现了一个：

✅ 原地逆置
✅ 时间复杂度 O(n)
✅ 空间复杂度 O(1)
✅ 泛型可复用

的 C++ 数组逆置模块。

通过这个看似简单的例子，你可以真正理解：

• 什么是'原地算法'
• 为什么双指针如此重要
• 模板在基础算法中的价值

常见问题及解答

Q1：为什么不新建一个数组？

答：

• 会增加空间复杂度
• 不符合很多算法题要求
• 原地算法更具工程价值

Q2：可以用递归实现吗？

答：

可以，但：

• 栈空间 O(n)
• 不如迭代版本高效、直观

Q3：std::reverse 和自己写有什么区别？

答：

• std::reverse 是高度优化的通用实现
• 自己实现是为了 理解算法本质

扩展方向与性能优化

区间逆置

ReverseArray(arr + l, r - l + 1);

字符串逆置

• 本质就是 char 数组逆置

结合双指针算法

• 回文判断
• 两数之和
• 滑动窗口

多维数组逆置（进阶）

• 行逆置
• 列逆置
• 矩阵旋转（90°）