评价指标
- 时间复杂度：分得细一点，可以是「最差时间复杂度」、「平均时间复杂度」、「最好时间复杂度」；
- 额外空间复杂度；
- 是否是原地排序；
- 稳定性；
各个排序的指标
| 最坏时间复杂度 | 平均时间复杂度 | 最好时间复杂度 | 额外空间复杂度 | 稳定性 | 是否原地排序 | |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(N^2) | O(N^2) | O(N) | O(1) | 稳定 | 原地排序 |
| 选择排序 | O(N^2) | O(N^2) | O(N^2) | O(1) | 不稳定 | 原地排序 |
| 插入排序 | O(N^2) | O(N^2) | O(N) | O(1) | 稳定 | 原地排序 |
| 希尔排序 | O(N^2) | O(n^(1.3-2)) | 没有研究 | O(1) | 不稳定 | 原地排序 |
| 归并排序 | O(NlogN) | O(NlogN) | O(NlogN) | O(N) | 稳定 | 非原地排序 |
| 快速排序 | O(N^2) | O(NlogN) | O(NlogN) | O(logN) | 不稳定 | 原地排序 |
| 堆排序 | O(NlogN) | O(NlogN) | O(NlogN) | O(1) | 不稳定 | 非原地排序 |
| 计数排序 | O(N + K) | O(N + K) | O(N + K) | O(N + K) | 稳定 | 非原地排序 |
| 基数排序 | O(NK) | O(NK) | O(N^2) | O(N + K) | 稳定 | 非原地排序 |
| 桶排序 | O(N^2) | O(N) | O(N) | 根据情况定 | 稳定 | 非原地排序 |
稳定性是指相等的元素在排序之后的相对位置没有改变；即对于相同的元素，原来靠前的元素在排序以后还靠前，原来靠后的元素在排序以后还靠后
原地排序是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序；
排序总结
选择排序 是一个不太灵活的排序方法，每一轮看完不能为下一轮提供有用的信息，而 插入排序、冒泡排序 可以提前检测到数组是否有序，以加快排序速度；选择排序 的优点是交换的次数最少，如果交换的成本比较大，适合使用 选择排序；
插入排序 在数组越有序的时候排序越快，这里有序指的是升序，如果数组是接近降序的话，插入排序会很慢；
快速排序 在数组越有序的时候排序越慢，因为越有序不管是升序还是降序，递归树的深度都增加，可以采用随机化切分元素的办法使得最差时间复杂度出现的概率大大降低；快速排序还特别适用于有大量重复值的元素的排序；
堆排序 是 选择排序 的优化，希尔排序 是 插入排序 的优化；归并排序 和 快速排序 都有各自的优化技巧，当处理的元素个数较少的时候，可以在 归并排序 和 快速排序 的子过程里使用插入排序；
打赏作者
您的打赏是我前进的动力
微信
支付宝
markdown 常用语法
上一篇
评论
