一、 分类描述
1. 插入排序
直接插入排序:算法简单,稳定,适用于数据量小的情况
希尔排序:直接插入排序的改进版,不稳定,对于待排序序列的不同情况效率相近
2. 交换排序
冒泡排序:算法简单,稳定,在数据基本有序的情况下效率较高
快速排序:算法效率高,不稳定,需要额外的辅助空间
3. 选择排序
直接选择排序:任何情况时间复杂度均为O(n^2),不稳定,其优势在于交换次数少
堆排序:不稳定,对序列的原始顺序不敏感,适用于数据量大的情况
4. 归并排序
分治策略,稳定,适用于待排序列整体无序、部分有序的情况,需要额外的辅助空间
5. 基数排序
稳定;适用范围有限;当数据位数较小时,时间复杂度近似为O(n),效率高于其它的稳定性排序算法
二、总结比较表
类别 |
排序方法 |
时间复杂度 |
空间复杂度 |
稳定性 |
复杂性 |
||
最好 |
最坏 |
平均 |
|||||
插入排序 |
直接插入 |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
O |
简单 |
希尔排序 |
O(n^1.3) |
O(n^2) |
O(n^1.x) |
O(1) |
X |
较复杂 |
|
交换排序 |
冒泡排序 |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
O |
简单 |
快速排序 |
O(nlogn) |
O(n^2) |
O(nlogn) |
O(logn) |
X |
较复杂 |
|
选择排序 |
直接选择 |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
X |
简单 |
堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
X |
较复杂 |
|
|
归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
O |
较复杂 |
|
基数排序 |
O(d(n+r)) |
O(d(n+r)) |
O(d(n+r)) |
O(n+r) |
O |
较复杂 |