排序算法的选择
排序算法的选择
一、算法汇总
| 算法 | 时间复杂度 | 空间复杂度 | 是否原地排序 | 是否稳定排序 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(1) | 是 | 是 |
| 插入排序 | O(n^2) | O(1) | 是 | 是 |
| 选择排序 | O(n^2) | O(1) | 是 | 否 |
| 归并排序 | O(nlogn) | O(n) | 否 | 是 |
| 快速排序 | O(nlogn) | O(1) | 是 | 否 |
| 桶排序 | O(n) | O(n) | 否 | 是 |
| 计数排序 | O(n) | O(n) | 否 | 是 |
| 基数排序 | O(n) | O(n) | 否 | 是 |
二、算法分析
| 算法 | 适用场景 | 不适用场景 |
|---|---|---|
| 冒泡排序 | 数据量小；稳定排序；原地排序 | 数据量大 |
| 插入排序 | 数据量小；稳定排序；原地排序 | 数据量大 |
| 选择排序 | 数据量小；原地排序 | 数据量大；稳定排序 |
| 归并排序 | 数据量小；稳定排序 | 数据量大；原地排序 |
| 快速排序 | 数据量大；原地排序 | 稳定排序 |
| 桶排序 | 数据总体分散局部聚集；稳定排序 | 原地排序 |
| 计数排序 | 数据量大但数值范围小 | 原地排序 |
| 基数排序 | 数据高低位有递进关系 | 原地排序 |
排序算法的一些数据和性能分析：
- 线性排序算法适用场景比较少，对数据要求比较高
- 归并排序需要 O(n) 的空间，不适用于大数据量的排序
- 选择排序是一种不稳定的排序算法
- 冒泡排序在性能上不如插入排序
不同算法都有各自的优缺点，应该根据实际情况选择不同的算法。
三、算法优化
3.1 插入排序
插入排序的优化，可以参考希尔排序。
3.2 快速排序
如果数据本身就是接近有序的，那么快速排序的复杂度可能会退化为 O(n^2)。
复杂度退化是由于分区点的选择不对，导致每次都不能很好地分成 2 部分数据。
分区点选择的优化方式有几种：
- 三数取中法
- 随机法
(1) 三数取中法
分别取左中右三个值，选择三个值中的中间值作为分区点。
这种方式可以较大程度上避免分区不合理的问题。
不过如当数据量比较大时，取 3 个数可能不太够，可以改成取 5 个、10 个等。
(2) 随机法
随机取一个元素作为分区点，随机的话基本上不容易出现最糟糕的情况。
四、综合优化
综上，快速排序和插入排序可能是比较好的选择：
- 在数据量比较小时，可以考虑插入排序和归并排序
- 在数据量比较大时，使用快速排序
选择算法时，应当根据实际的数据情况来选择。