知识卡片
组合排序按退化风险换策略
内省排序保留快速分区的常见效率,同时监控可能退化的过程,必要时切换到堆排序来限制最坏风险。重点是不同阶段采用不同策略,而非只对同一种算法再调几个常数。
补充核验:LLVM libc++的introsort说明在深度预算耗尽时回退堆排序,表明“检测”可以具体落实为分区深度控制。官方sort.h相关分支(2026-11-06读取搜索呈现的__introsort/深度回退代码)。这只是补充机制示例,不宣称完整读过该库或本书实现了内省排序。
原文“某些情况略快”不等于所有输入都更快;正确最坏界仍需正确分区、深度限制和回退算法共同成立。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
内省排序 一种类似于快速排序的排序算法,只是在检测时,它会切换到堆排序,从而提高排序效率。由于这点改进,在某些情况下它会比快速排序效率略高。 桶排序 一种线性排序算法,用来对均匀随机分布的数据进行排序。它的工作原理是,首先将数据分散到一些桶中,然后将桶中的数据排序,从而最后形成一个有序数据集。
参考来源
- 位置:《算法精解:C语言描述》第12章《相关主题》(spine1358;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1324.html;u226-ch12-025)。
- 结论依据:226内省短段实读,官方LLVM代码相关深度耗尽注释与分支核验,不从名称空造触发条件或当前版本性能推荐。
- 原始内容:内省排序 一种类似于快速排序的排序算法,只是在检测时,它会切换到堆排序,从而提高排序效率。由于这点改进,在某些情况下它会比快速排序效率略高。 桶排序 一种线性排序算法,用来对均匀随机分布的数据进行排序。它的工作原理是,首先将数据分散到一些桶中,然后将桶中的数据排序,从而最后形成一个有序数据集。