知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.16 · 生成模型:未记录

内省排序以深度限制兜底

理解等级:中级

先执行快速排序,给分区递归设置与初始规模对数成比例的深度预算;预算耗尽时对剩余区间切换堆排序,并可对小区间采用插入排序。快排部分每层总工作量为 O(n),层数受限于 O(log n),堆排序兜底提供最坏 O(n log n)。

三数取中和固定插入排序阈值只是经验优化,不单独保证最坏界。书中说只有使用BFPRT才可保证该界过于绝对,紧接的内省排序就是另一种办法。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      内观排序 是否切换到对小数组的插入排序取决于数组的大小。Musser(1997)介绍了一个快速排序的变种,叫做内观排序(IntroSort),这个算法监视快速排序的递归深度,以确保高效地处理。如果快速排序的递归深度超过log(n)级,那么内观排序切换到堆排序。C++STL的SGI实现使用了内观排序作

    参考来源

    - 位置:《算法技术手册》第4章《变种》(spine1511;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1474.html;u084-ch04-017)。 - 结论依据:84全文实读;复杂度保证依赖正确实现的深度预算和堆排序。 - 原始内容:内观排序 是否切换到对小数组的插入排序取决于数组的大小。Musser(1997)介绍了一个快速排序的变种,叫做内观排序(IntroSort),这个算法监视快速排序的递归深度,以确保高效地处理。如果快速排序的递归深度超过log(n)级,那么内观排序切换到堆排序。C++STL的SGI实现使用了内观排序作