原地排序（In-place Sort）
定义
原地排序是指仅需 O(1) 额外空间（不算输入数组本身）的排序算法。算法通过直接修改输入数组来完成排序，不需要额外的数组来存储中间结果。
核心特性
| 特性 |
说明 |
| 空间复杂度 |
O(1)（仅需常数级额外变量） |
| 实现方式 |
通过元素交换或移动，直接在原数组上操作 |
| 优点 |
节省内存，适合内存受限场景 |
| 缺点 |
实现可能较复杂，某些算法（如堆排序）实际性能可能不如预期 |
常见原地排序算法
| 算法 |
时间复杂度（平均） |
稳定性 |
说明 |
| 选择排序 |
O(n²) |
不稳定 |
每轮选最小值与当前位置交换 |
| 插入排序 |
O(n²) |
稳定 |
但实现通常是原地的 |
| 希尔排序 |
O(n^1.3) |
不稳定 |
插入排序的改进 |
| 快速排序 |
O(n log n) |
不稳定 |
原地 partition，递归栈空间 O(log n) |
| 堆排序 |
O(n log n) |
不稳定 |
基于二叉堆的原地排序 |
| 冒泡排序 |
O(n²) |
稳定 |
原地交换相邻元素 |
非原地排序算法
| 算法 |
空间复杂度 |
说明 |
| 归并排序 |
O(n) |
需要额外数组进行合并 |
| 计数排序 |
O(k) |
需要计数数组 |
| 桶排序 |
O(n+k) |
需要额外桶空间 |
| 基数排序 |
O(n+k) |
需要额外桶空间 |
快速排序的原地性说明
虽然快速排序的递归调用需要 O(log n) 的栈空间，但通常仍被认为是原地排序，因为：
- 主要操作（partition）是原地完成的
- 递归栈空间不算作"额外空间"（是函数调用开销）
- 与归并排序的 O(n) 额外空间相比，可以忽略
相关概念
- 排序算法：原地排序是排序算法的重要评估指标
- 空间复杂度：原地排序的空间复杂度为 O(1)
- 稳定排序：原地与原地是不同维度，可组合（如插入排序：原地+稳定）
- 堆排序：典型的原地排序算法
- 快速排序：平均 O(n log n) 的原地排序