一.排序算法复杂度
|
排序算法 |
时间复杂度 |
空间复杂度(最坏情形) |
||
|
最好 |
平均 |
最坏 |
||
|
冒泡排序 |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
|
插入排序 |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
|
归并排序 |
O(n*log(n)) |
O(n*log(n)) |
O(n*log(n)) |
O(n) |
|
快速排序 |
O(n*log(n)) |
O(n*log(n)) |
O(n^2) |
O(n) |
|
堆排序 |
O(n*log(n)) |
O(n*log(n)) |
O(n*log(n)) |
O(1) |
|
桶排序 |
O(n+k) |
O(n+k) |
O(n^2) |
O(nk) |
|
基数排序 |
O(nk) |
O(nk) |
O(nk) |
O(n+k) |
二.使用比较的排序算法下界
上面的二叉树建立了决策树的模型，可以得出的结论是：任意N个数，它们的排列方式有N!种，使用比较排序，至少要比较log(N!)次（树的深度）。这可以用于证明排序算法的下界。只使用元素间比较的任何排序算法需要进行Ω（NlogN）次比较。
证明：使用比较的排序需要进行log(N!)次比较，log(N!) =log(N(N-1)(N-2)(N-3)(N-4)…1)
>=logN+log(N-1)+…log(N/2)
>=N/2log(N/2)
=N/2log(N)-N/2
=Ω(NlogN)
原文：http://blog.csdn.net/u011608357/article/details/21780093
