introsort的大致思想是:当数据很大时先用quicksort,当递归超过一定深度时改用heapsort,最后每个子序列元素个数达到16时改用insertionsort
STL:sort 貌似也是introsort,希尔排序效率不是比堆排序好点吗,难道是处理大数据时的实际效率比不过堆排序?
为什么introsort(内省排序)里用堆排序而不是希尔排序?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- Coursera 2014-12-02 18:35关注
quicksort,mergesort和heap sort都是最优和平均情况下都是O(nlogn)的算法, shell sort虽然最优是n(sorted),但是平均是O(nlog^2n)。在考虑实现时,大家考虑的平均情况,而不是最好的情况。
解决 无用评论 打赏 举报
悬赏问题
- ¥15 关于#matlab#的问题:期望的系统闭环传递函数为G(s)=wn^2/s^2+2¢wn+wn^2阻尼系数¢=0.707,使系统具有较小的超调量
- ¥15 FLUENT如何实现在堆积颗粒的上表面加载高斯热源
- ¥30 截图中的mathematics程序转换成matlab
- ¥15 动力学代码报错,维度不匹配
- ¥15 Power query添加列问题
- ¥50 Kubernetes&Fission&Eleasticsearch
- ¥15 報錯:Person is not mapped,如何解決?
- ¥15 c++头文件不能识别CDialog
- ¥15 Excel发现不可读取的内容
- ¥15 关于#stm32#的问题:CANOpen的PDO同步传输问题