| 排序算法 |
平均时间复杂度 |
辅助空间 |
稳定性 |
| 插入排序 |
n2 |
1 |
稳定 |
| 选择排序 |
n2 |
1 |
不稳定 |
| 冒泡排序 |
n2 |
1 |
稳定 |
| shell排序 |
n1.3 |
1 |
不稳定 |
| 快速排序 |
nlog(n) |
log(n) |
不稳定 |
| 堆排序 |
nlog(n) |
1 |
不稳定 |
| 归并排序 |
nlog(n) |
n |
稳定 |
| 基数排序 |
d(n+d) |
rd |
稳定 |
根据上面的表格得到下面的几个结论:
1.如果数据量比较小，则可以倾向于选择插入排序和选择排序。
2.如果数据基本排序成功，则可以倾向于选择插入排序和冒泡排序。
3.如果数据量比较大，并且关键字的位数比较小的时候，则可以选择链式基数排序。
4.如果数据量比较大，则选择时间复杂度比较小的快速排序，归并排序和堆排序。