什么是排序算法的稳定性？
- 稳定排序: 相等元素的相对次序在排序后保持不变;
- 判定方法: 只在严格逆序时交换 (如
nums[j] > nums[j + 1]), 相等时不换位即稳定;
- 用途: 多关键字排序时先按次要关键字排, 再稳定地按主要关键字排;
各类排序算法的时间与空间复杂度如何对比？
| 算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|
| 选择排序 | O(n^2) | O(1) | 非稳定 |
| 冒泡排序 | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n log n) ~ O(n^2) | O(1) | 非稳定 |
| 快速排序 | 平均 O(n log n), 最差 O(n^2) | 平均 O(log n), 最差 O(n) | 非稳定 |
| 归并排序 | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(1) | 非稳定 |
| 桶排序 | O(n + k), k 为桶数 | O(n + k) | 取决于桶内排序 |
| 计数排序 | O(n + m), m 为取值范围 | O(n + m) | 稳定 |
| 基数排序 | O(nk), k 为最大位数 | O(n + d), d 为基数 | 稳定 |
如何按场景选择排序算法？
- 小数据量: 插入排序, 常数小且实现简单;
- 通用大数据量: 快速排序, 但需防基准数劣化; 或归并排序, 稳定且与输入无关;
- 要求常数级额外空间: 堆排序;
- 取值范围有限: 计数排序; 值域可映射为数字: 桶排序; 位数少而范围大: 基数排序;
- 要求稳定且时间 O(n log n): 归并排序、基数排序;