切换主题
排序算法总结
| 排序算法 | 如何优化 | 内/外 | 稳定性 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|---|
| 冒泡排序 | 双向冒泡 | In | Y | O(n^2) | O(1) |
| 选择排序 | 二元选择 | In | N | O(n^2) | O(1) |
| 插入排序 | 希尔排序 | In | Y | O(n^2) | O(1) |
| 希尔排序 | 增量序列 | In | N | O(nlogn) | O(1) |
| 堆排序 | / | In | N | O(nlogn) | O(1) |
| 快速排序 | / | In | N | O(nlogn) | O(logn) |
| 归并排序 | / | Out | Y | O(nlogn) | O(n) |
| 计数排序 | / | Out | Y | O(n) | O(k) |
| 基数排序 | / | Out | Y | O(n) | O(n+k) |
| 桶排序 | / | Out | Y | O(n) | O(n+k) |
特别注意：
- 稳定性（指
可以做到稳定，并不是一定稳定）定义为相同值的元素在排序后相对位置不变 - 不存在
基于比较的排序：- 其时间复杂度小于
O(nlogn) - 其时间复杂度为
O(nlogn)，空间复杂度在O(n)以下的稳定排序
- 其时间复杂度小于
- 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至
O(n)；而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O(n^2)； - 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大；
- 计数排序为非比较排序，适用于数据量大但是范围小的排序。