to myself 的分类学习日志

做自己想做的事
posts - 232, comments - 6, trackbacks - 0, articles - 0

常用的排序算法的时间复杂度和空间复杂度

原文:http://www.cnitblog.com/houcy/archive/2009/07/24/60349.html

sort

 

sort2



考点:各排序算法时间复杂度比较
出现频率:★★★
写出下列算法的时间复杂度。
(1)冒泡排序;
(2)选择排序;
(3)插入排序;
(4)快速排序;
(5)堆排序;
(6)归并排序;
答案:
冒泡排序算法时间复杂度是O(n^2)。
选择排序算法复杂度是O(n^2)。
插入排序算法时间复杂度是O(n^2)
快速排序快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n),最坏O(n^2)。
堆排序算法时间复杂度O(nlogn)。
归并排序的时间复杂度是O(nlog2n)。


参考:
1, http://en.wikipedia.org/wiki/Sorting_algorithm





只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理