之前学习排序算法的时候一直纠结于复杂度问题,原因是网上查到的算法复杂度略有出入,所以本人特地整理了一份,方便大家学习。
记住一句话:冒择路(入)兮(希尔)快归堆
算法名称 |
最好 |
平均 |
最坏 |
辅助空间 |
稳定性 |
|
插入 |
直接插入 |
O(n) |
O(n^2) |
1 |
稳定 |
|
折半插入 |
O(nlogn) |
1 |
稳定 |
|||
希尔排序ShellSort |
O(nlogn) |
1 |
不稳定 |
|||
交换 |
冒泡排序BubbleSort |
O(n) |
O(n^2) |
1 |
稳定 |
|
快速排序QuickSort |
O(nlogn) |
O(n^2) |
logn |
不稳定 |
||
选择 |
选择排序Selection |
O(n^2) |
1 |
不稳定 |
||
堆排序HeapSort |
O(nlogn) |
1 |
不稳定 |
|||
其他 |
归并排序MergeSort |
O(nlogn) |
n |
稳定 |
||
基数排序RadixSort |
O(nd),d是常数 |
n |
稳定 |
|||
二叉树Binarytree |
O(nlogn) |
n |
稳定 |
|||
桶排序BucketSort |
O(n) |
k |
稳定 |