2 u011456891 u011456891 于 2014.12.02 16:54 提问

为什么introsort(内省排序)里用堆排序而不是希尔排序?

introsort的大致思想是:当数据很大时先用quicksort,当递归超过一定深度时改用heapsort,最后每个子序列元素个数达到16时改用insertionsort
STL:sort 貌似也是introsort,希尔排序效率不是比堆排序好点吗,难道是处理大数据时的实际效率比不过堆排序?

1个回答

eagleyan
eagleyan   Rxr 2014.12.03 02:35

quicksort,mergesort和heap sort都是最优和平均情况下都是O(nlogn)的算法, shell sort虽然最优是n(sorted),但是平均是O(nlog^2n)。在考虑实现时,大家考虑的平均情况,而不是最好的情况。

eagleyan
eagleyan 回复u011456891: ok, puzzle solved
大约 3 年之前 回复
u011456891
u011456891 回复eagleyan:通过前面那个评论我懂了。还有 ,那个O(1)是我改的。。
大约 3 年之前 回复
eagleyan
eagleyan 我希望你仔细看这个表格、里面memory列指的空间复杂度、写的就是1。顺便说一句、wikipedia在资料权威性方面是相当高的、虽然有人质疑上面对些历史事件的描述有政治倾向性、但对计算机排序这种东西的描述远比你读的书要准确。wikipedia是不断修正的
大约 3 年之前 回复
eagleyan
eagleyan 我希望你仔细看这个表格、里面memory列指的空间复杂度、写的就是1。顺便说一句、wikipedia在资料权威性方面是相当高的、虽然有人质疑上面对些历史事件的描述有政治倾向性、但对计算机排序这种东西的描述远比你读的书要准确。wikipedia是不断修正的
大约 3 年之前 回复
u011456891
u011456891 回复eagleyan: 这上面的不准确,比如希尔排序本来是原址排序,它上面的空间复杂度却不是O(1)
大约 3 年之前 回复
eagleyan
eagleyan 回复u011456891: 我想你混淆了算法复杂度和实际每步的指令数,在考虑算法效率的时候,O(h)是大家最关心的指数,有的时候两个算法当中某个O(h)的值较小,但单步的指令数多几步,在数据较少的时候,可能还慢一点,但是一旦数据量上去了,速度远比复杂度差的效率高。
大约 3 年之前 回复
u011456891
u011456891 数据结构与算法分析c++版 说过 堆排序移动数据要进行2次比较,就是说即使平均时间复杂度小于希尔排序,但它每次循环进行的操作效率低于希尔排序,实际效率就可能低于希尔排序
大约 3 年之前 回复
eagleyan
eagleyan 数据来源:wikipedia - http://en.wikipedia.org/wiki/Sorting_algorithm
大约 3 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!