常用的排序算法的时间复杂度和空间复杂度
原文:http://www.cnitblog.com/houcy/archive/2009/07/24/60349.html
考点:各排序算法时间复杂度比较
出现频率:★★★
写出下列算法的时间复杂度。
(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