C++：实现数组逆置（附带源码）
一、项目背景详细介绍
在所有编程语言与算法体系中，数组逆置（Reverse） 都是一个极其基础、却又极其重要的操作。
你几乎一定在以下场景中见过它：
- 数据预处理（反转序列）
- 算法步骤中的子过程（如双指针）
- 字符串反转、本质就是数组逆置
- 栈结构的底层思想
- 面试中 100% 会出现的基础题
看似简单的一句：
reverse(arr.begin(), arr.end());
背后实际上蕴含着：
- 指针 / 下标的本质
- 原地算法思想
- 时间与空间复杂度分析
- 泛型设计能力
1. 为什么“数组逆置”值得单独讲？
原因很简单：
这是理解“算法基本功”的分水岭
很多初学者的问题不是“不会写”，而是：
- 写不清楚
- 写不通用
- 写不安全
- 说不明白复杂度
而数组逆置，正好是一个可以把这些问题一次性讲透的例子。
2. 常见错误实现
初学者常见写法包括：
for (int i = 0; i < n; ++i) newArr[i] = arr[n - 1 - i];
问题在于：
- ❌ 额外空间 O(n)
- ❌ 不是真正“逆置原数组”
- ❌ 不具备工程通用性
3. 本项目目标
本项目将：
- 从最基础的一维数组逆置开始
- 逐步扩展到：
- 指针版
- STL 容器版
- 泛型模板版
- 严格分析：
- 时间复杂度
- 空间复杂度
- 最终形成一个 工程级可复用数组逆置方案
二、项目需求详细介绍
1. 功能需求
实现数组逆置功能，支持：
- C 风格数组
- 指针 + 长度形式
std::vector- 泛型模板逆置
2. 算法要求
- 原地逆置（in-place）
- 不使用额外数组
- 时间复杂度 O(n)
- 空间复杂度 O(1)
3. 教学要求
- 代码必须清晰
- 注释必须详细
- 适合课堂与博客直接使用
三、相关技术详细介绍
1. 什么是数组逆置？
给定一个数组：
[1, 2, 3, 4, 5]
逆置后的结果为：
[5, 4, 3, 2, 1]
2. 原地逆置（In-place）的含义
原地算法指的是：
不依赖与输入规模成正比的额外空间
数组逆置的经典原地实现方式是：
对称位置元素交换
3. 双指针思想
设置两个指针：
left：指向数组开头right：指向数组末尾
不断交换，直到二者相遇。
4. 时间与空间复杂度分析
- 时间复杂度：
每个元素最多参与一次交换 → O(n) - 空间复杂度：
只使用常数个临时变量 → O(1)
四、实现思路详细介绍
1. 核心算法流程
left = 0 right = n - 1 while left < right: swap(arr[left], arr[right]) left++ right--
2. 为什么循环条件是 left < right？
- 当
left == right：中间元素无需交换 - 当
left > right：已经完成逆置
3. swap 的本质
交换两个元素，本质是：
- 使用一个临时变量
- 或调用
std::swap
4. 扩展到泛型的关键
- 使用模板
- 只要求类型支持拷贝 / 交换
五、完整实现代码
/************************************************************ * 文件：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; } 六、代码详细解读（仅解读方法作用）
1. ReverseArray(T* arr, size_t length)
作用：
- 对任意类型的一维数组进行原地逆置
- 使用双指针法
- 不依赖额外空间
2. ReverseArray(std::vector<T>&)
作用：
- 为 STL 容器提供友好接口
- 内部复用指针版本实现
- 保证逻辑一致性
3. std::swap 的作用
作用：
- 交换两个对象
- 内部可针对类型进行优化
- 泛型算法首选
七、项目详细总结
本项目实现了一个：
✅ 原地逆置
✅ 时间复杂度 O(n)
✅ 空间复杂度 O(1)
✅ 泛型可复用
的 C++ 数组逆置模块。
通过这个看似简单的例子，你可以真正理解：
- 什么是“原地算法”
- 为什么双指针如此重要
- 模板在基础算法中的价值
八、项目常见问题及解答
Q1：为什么不新建一个数组？
答：
- 会增加空间复杂度
- 不符合很多算法题要求
- 原地算法更具工程价值
Q2：可以用递归实现吗？
答：
可以，但：
- 栈空间 O(n)
- 不如迭代版本高效、直观
Q3：std::reverse 和自己写有什么区别？
答：
std::reverse是高度优化的通用实现- 自己实现是为了 理解算法本质
九、扩展方向与性能优化
1. 区间逆置
ReverseArray(arr + l, r - l + 1);
2. 字符串逆置
- 本质就是
char数组逆置
3. 结合双指针算法
- 回文判断
- 两数之和
- 滑动窗口
4. 多维数组逆置（进阶）
- 行逆置
- 列逆置
- 矩阵旋转（90°）
