排序算法 (Sorting Algorithm)
将一组数据按照特定顺序（如从小到大）排列的算法集合，是计算机科学中最基础的算法类别之一。
定义
排序算法是指将一组无序数据按照特定比较规则（通常是数值大小或字典序）重新排列成有序序列的算法。
核心评估指标
根据排序算法的关键指标，评估排序算法需要从三个维度综合考虑：
| 指标 | 说明 |
|---|---|
| 时间复杂度 | 算法执行时间随输入规模增长的渐近趋势 |
| 空间复杂度 | 算法占用额外存储空间的情况 |
| 排序稳定性 | 相同元素排序后相对位置是否保持不变 |
| 是否原地排序 | 是否只需常数级额外空间（O(1)） |
稳定排序 vs 不稳定排序
-
稳定排序：相同元素的相对位置在排序后不变
- 实际意义：多字段排序时，保持上层排序的层次性
- 示例：先按日期排序订单，再按用户ID排序，稳定排序可保持同用户的日期有序性
-
不稳定排序：相同元素的相对位置可能改变
- 示例：选择排序因交换操作导致不稳定
时间复杂度对比
| 算法 | 时间复杂度（平均） | 空间复杂度 | 稳定性 | 原地排序 |
|---|---|---|---|---|
| 选择排序-总结 | O(n²) | O(1) | 不稳定 | 是 |
| 插入排序 | O(n²) | O(1) | 稳定 | 是 |
| 冒泡排序 | O(n²) | O(1) | 稳定 | 是 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 | 否* |
| 归并排序 | O(n log n) | O(n) | 稳定 | 否 |
| 堆排序 | O(n log n) | O(1) | 不稳定 | 是 |
*快速排序递归栈空间 O(log n)，若用迭代实现可视为原地
常见类型
1. 基础排序算法（O(n²)）
- 选择排序：每次选择最小值放到已排序末尾，不稳定，O(n²)
- 插入排序：将元素插入到已排序部分的正确位置，稳定，O(n²)
- 冒泡排序：通过交换相邻逆序对完成排序，稳定，支持提前终止
冒泡排序详解
算法思想：倒序遍历未排序部分，发现逆序对就交换相邻元素，让最小值逐步"冒泡"到正确位置。
核心特点：
- 稳定排序：只交换相邻元素，不改变相同元素的相对位置
- 提前终止：添加
swapped标志，若一轮无交换说明数组已有序，可提前退出（最好情况 O(n)） - 原地排序：空间复杂度 O(1)
与选择排序对比：
| 维度 | 冒泡排序 | 选择排序 |
|---|---|---|
| 稳定性 | 稳定 | 不稳定 |
| 最好情况 | O(n)（提前终止） | O(n²)（无法优化） |
| 交换次数 | 较多（每对逆序都交换） | 较少（每轮只交换一次） |
三个优化阶段（从选择排序演进）：
- 用数据搬移替代交换 → 获得稳定性（但增加额外循环）
- 合并查找与搬移操作 → 真正的冒泡排序，消除额外循环
- 添加提前终止 → 利用数组有序度，近乎有序时效率显著提升
2. 高效排序算法（O(n log n)）
- 快速排序：分治思想，选取基准元素分区
- 归并排序：分治思想，先分后合
- 堆排序：利用二叉堆的数据结构特性
3. 特殊场景排序
- 计数排序：适用于整数且范围有限的场景，O(n+k)
- 桶排序：将数据分到多个桶中分别排序
- 基数排序：按位排序，从低位到高位
选择排序详解
选择排序-总结是最简单的排序算法之一：
算法思想：每次从未排序部分选择最小值，放到已排序部分的末尾。
特点：
- 时间复杂度 O(n²)，嵌套循环执行 n²/2 次
- 空间复杂度 O(1)，原地排序
- 不是稳定排序：交换操作会打乱相同元素的相对顺序
- 即使数组已有序，仍执行相同次数
优化尝试：作者尝试用 suffixMin 数组预计算后缀最小值，但因交换操作导致 nums 变化，预计算失效，无法优化。
注意事项
- 时间复杂度仅关注量级（最高次项），但实际应用需关注实际执行次数
- 数组本身有序度对选择排序的时间复杂度无影响
- 交换操作是导致选择排序不稳定的根本原因
- 选择排序无法优化时间复杂度，后续算法（如插入排序）会改进这一点
应用场景
- O(n²) 算法：适用于小规模数据排序
- O(n log n) 算法：大规模数据排序的标准选择
- 稳定排序：多字段排序场景（如先按日期、再按用户ID）
- 原地排序：内存受限环境
经典算法
- 选择排序-总结：最简单的排序算法，O(n²)
- 插入排序：适合近乎有序的数组，O(n²) 但常数项小
- 快速排序：实践中最快的通用排序算法之一
- 归并排序：稳定的 O(n log n) 排序，需要额外空间