6.1 如何选择合适的排序算法
选择合适的排序算法需要考虑多个因素：
| 场景 | 推荐算法 | 理由 |
|---|---|---|
| 大规模基本类型数据 | 快速排序 | 平均性能最好，缓存友好 |
| 大规模对象数据 | 归并排序（TimSort） | 稳定，性能稳定 |
| 小规模数据（n < 50） | 插入排序 | 常数因子小，简单 |
| 数据基本有序 | 插入排序或冒泡排序 | 适应性好 |
| 内存受限 | 堆排序或希尔排序 | 原地排序，不需要额外空间 |
| 需要稳定排序 | 归并排序或基数排序 | 保持相等元素顺序 |
| 整数且范围有限 | 基数排序或桶排序 | 线性时间复杂度 |
| 链表排序 | 归并排序 | 天然适合链表 |
| 数据均匀分布 | 桶排序 | 平均 O(n) |
| 需要实时排序 | 插入排序 | 在线算法 |