内部排序方法比较
综合对比
总结
| 排序方法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 直接插入 | O(n²) | O(n²) | O(1) | 稳定 |
| 折半插入 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n¹·³) | O(n²) | O(1) | 不稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 简单选择 | O(n²) | O(n²) | O(1) | 不稳定 |
| 树形选择 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(n+k) | 稳定 |
选择建议
- 数据量小：直接插入排序
- 数据基本有序：直接插入排序或冒泡排序
- 数据量大且对稳定性有要求：归并排序
- 数据量大且对空间有要求：快速排序或堆排序
- 关键字可拆分：基数排序
链接到
- 上一个知识点：6.11 基数排序
- 下一个知识点：无（本章最后一个知识点）