|
名称 |
稳定性 |
时间复杂度 |
空间复杂度 |
描述 |
数据对象为链表 |
||
|
平均 |
最坏 |
||||||
|
冒泡排序 |
Y |
O(n^2) |
O(1) |
无序区，有序区。 |
|
||
|
选择排序 |
|
O(n^2) |
O(1) |
有序区，无序区 |
稳定性Y,其它同数组 |
||
|
插入排序 |
Y |
O(n^2) |
O(1) |
有序区，无序区 |
同数组 |
||
|
堆排序 |
|
O(n log n) |
O(1) |
最大堆，有序区 |
|
||
|
归并排序 |
Y |
O(n log n) |
O(n)+O(log n) |
将数据分为两段，逐段排序 |
空间复杂度O(1) |
||
|
快速排序 |
|
O(n log n) |
O(n^2) |
O(log n)-O(n) |
选择基数，调整方位 |
|
|
|
希尔排序 |
|
O(n log n) |
O(n^2) |
O(1) |
每次循环按间隔进行插入排序 |
|
|
快速排序针对小数目数组列表的优化为最佳的排列方法。
原文：http://www.cnblogs.com/aprilapril/p/4309221.html