1. 简介
本文将深入讲解原地排序算法（In-Place Sorting Algorithm）的工作原理。我们不仅会从概念上剖析其核心思想，还会通过伪代码对比、Java 实现以及常见算法举例，帮助你真正理解“原地”这一关键特性在实际开发中的意义和优势。
对于有经验的开发者来说，这类知识不仅是面试常客，更是优化性能时绕不开的底层逻辑。
2. 什么是原地算法
✅ 原地算法（in-place algorithm） 是指在执行过程中不需要额外辅助数据结构来处理输入数据的算法。换句话说，它直接在原始输入数据上进行操作，用输出结果覆盖原始输入。
⚠️ 注意：这里的“不额外使用空间”是理想化说法。实际上，算法可能会使用少量、非恒定的临时变量（比如循环计数器或交换用的 temp），但这些空间复杂度通常为 O(1) 或最多 O(log n) —— 只要不是线性增长（O(n)），一般仍视为原地操作。
举个例子：
- ✅ 原地反转数组：只用一个
temp变量完成元素交换 - ❌ 非原地反转：新建一个数组复制反向内容，空间开销 O(n)
因此判断是否为原地操作，关键看额外空间是否随输入规模线性增长。
3. 伪代码对比：原地 vs 非原地
我们以“反转数组”为例，直观对比两种实现方式的差异。
3.1 原地反转（In-Place）
核心思路：首尾两两交换，中间用一个临时变量暂存值。只需要遍历一半数组即可完成。
reverseInPlace(array A[n])
for i from 0 to n/2
temp = A[i]
A[i] = A[n - 1 - i]
A[n - 1 - i] = temp
📌 特点：
- ✅ 额外空间：O(1) —— 仅
temp和i - ✅ 时间复杂度：O(n)
- ✅ 空间效率高，适合大数组场景
下图展示了原地反转的过程（原数组被逐步覆盖）：
3.2 非原地反转（Out-of-Place）
做法更直观：创建一个新数组，按反向顺序复制元素，最后返回新数组。
reverseOutOfPlace(array A[n])
create new array B[n]
for i from 0 to n - 1
B[i] = A[n - 1 - i]
delete A
return B
📌 特点：
- ❌ 额外空间：O(n) —— 新建了完整副本
- ✅ 时间复杂度：O(n)
- ⚠️ 创建/销毁数组开销大，GC 压力增加
适合对原始数据有保留需求的场景，但一般不推荐用于性能敏感路径。
过程示意如下：
4. Java 实现示例
4.1 原地反转实现
public static int[] reverseInPlace(int A[]) {
int n = A.length;
for (int i = 0; i < n / 2; i++) {
int temp = A[i];
A[i] = A[n - 1 - i];
A[n - 1 - i] = temp;
}
return A;
}
📌 踩坑提醒：该方法会修改原始数组！调用前务必确认是否可变。
测试用例：
@Test
void givenArray_whenInPlaceSort_thenReversed() {
int[] input = {1, 2, 3, 4, 5, 6, 7};
int[] expected = {7, 6, 5, 4, 3, 2, 1};
assertArrayEquals("the two arrays are not equal", expected,
InOutSort.reverseInPlace(input));
}
4.2 非原地反转实现
public static int[] reverseOutOfPlace(int A[]) {
int n = A.length;
int[] B = new int[n];
for (int i = 0; i < n; i++) {
B[n - i - 1] = A[i];
}
return B;
}
📌 优点：原始数组不受影响，函数更“纯”。
测试用例：
@Test
void givenArray_whenOutOfPlaceSort_thenReversed() {
int[] input = {1, 2, 3, 4, 5, 6, 7};
int[] expected = {7, 6, 5, 4, 3, 2, 1};
assertArrayEquals("the two arrays are not equal", expected,
InOutSort.reverseOutOfPlace(input));
}
5. 常见原地排序算法举例
以下是一些典型的原地排序算法，它们的空间复杂度均控制在 O(log n) 或 O(1)：
| 算法 | 是否原地 | 空间复杂度 | 备注 |
|---|---|---|---|
| ✅ 插入排序（Insertion Sort） | 是 | O(1) | 小数据集高效 |
| ✅ 冒泡排序（Bubble Sort） | 是 | O(1) | 教学用途为主 |
| ✅ 快速排序（Quicksort） | 是 | O(log n) | 平均性能优秀，递归栈开销 |
| ✅ 堆排序（Heapsort） | 是 | O(1) | 最坏情况 O(n log n) |
| ✅ 希尔排序（Shell Sort） | 是 | O(1) | 插入排序的改进版 |
| ✅ 梳排序（Comb Sort） | 是 | O(1) | 冒泡排序的优化 |
⚠️ 注意：虽然快速排序使用递归导致栈空间 O(log n)，但由于该空间不随输入成线性增长，仍被归类为原地算法。
📌 延伸建议：
- 学习 插入排序 和 快速排序 的 Java 实现
- 掌握 大 O 表示法（Big-O Notation） 的理论基础
- 查阅 Java 算法复杂度实战分析 获取更多性能对比案例
6. 总结
本文系统性地介绍了原地算法的核心概念，并通过数组反转这一简单但典型的例子，展示了原地与非原地实现的本质区别：
- ✅ 原地操作节省内存，适合大规模数据处理
- ❌ 非原地操作安全但代价高，需权衡使用场景
- 🔧 实际开发中应优先考虑原地优化，尤其是在资源受限环境
所有示例代码已托管至 GitHub，欢迎参考：
👉 https://github.com/eugenp/tutorials/tree/master/algorithms-modules/algorithms-sorting-2