首页 > 代码库 > 九种常用排序的性能分析总结

九种常用排序的性能分析总结

转自:http://blog.csdn.net/cjf_iceking/article/details/7953637

 

间间断断的将9种排序实现,并且将其以博客笔记的形式记录下来;现在就该来综合的分析这九种排序,让我们先来看看其算法复杂度和稳定性的分析结果:

算法复杂度以及稳定性分析

算法名称平均时间辅助空间稳定性
冒泡排序O(n2)O(1)
选择排序O(n2)O(1)
插入排序O(n2)O(1)
自底向上归并排序O(nlog2n)O(n)
自顶向下归并排序O(nlog2n)O(n)
快速排序O(nlog2n)O(n)
堆排序O(nlog2n)O(1)
基数排序O(dn)O(rn)
希尔排序\O(1)

排序的时间效率比较

下图表名了各种算法在不同数据规模下,完成排序所消耗的时间(毫秒为单位),从表中可以显然看出O(n2)的排序算法比O(nlog2n)的算法 时间多出几百上千倍,而且随着数据数据规模增大时间比也会随着增大;因为排序的数据采用随机数,顺序将被打乱,快速排序算法优于其他排序算法!
算法名称1万2万3万4万5万6万7万8万9万10万
冒泡排序14425497122062186134017491486739488880111939139071
选择排序19981617903254506271669645126361610219643
插入排序17871716282882445864468822116491454717914
自底向上归并排序36912151822262833
自顶向下归并排序371115182327313640
快速排序25811141821252932
堆排序371216192326303437
基数排序9213040495966759098
希尔排序381115242429354041

下面采用图表形式将数据直观展示出来(将O(n2)的算法和O(nlog2n)算法分开,因为完全不是一个数量级的):
上图显示快排速度和自底向上归并排序奇虎相当,接下来是堆排序、希尔排序;出乎意料的是基数排序,号称O(dn)的基数排序却不是那么靠前,个人觉得和冒泡排序速度慢的原因相同,赋值操作太多,降低了时间效率。
 
 
修正更新:
 2012-9-13
【1】 修改归并排序的代码,并重新生成测试结果 
【2】 上传九种排序的实现代码(下载地址:http://download.csdn.net/detail/cjf_iceking/4567202)

 

九种常用排序的性能分析总结