知识卡片

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

快速选择维护相对子区间的秩

理解等级:中级

在闭区间 [left,right] 寻找第 k 小,k 从1开始。分区返回 p 后,中枢相对秩为 p−left+1;若目标更小则保留 k 并搜索左区间,若更大则搜索右区间并令 k 减去该相对秩。函数返回的是数组索引,不是元素值。

这个换算在 left 不为零时不可省略。调用者应保证区间有效且 1≤k≤right−left+1;示例代码没有显式验证。随机中枢对互异元素可得到期望线性选择时间,但分区把等值全部放左侧,所有键相等时仍可能每次只缩小一项,导致二次时间。

75指出可将尾递归改写为循环:每轮分区后更新 left、right 和必要时的 k,命中目标后返回索引。这样可避免递归栈增长,但不会消除重复键导致的分区退化。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      selectKth是一个平均时间为线性的函数,给定一个适当的pivotIndex,其返回了数组ar中的第k个元素,例4-4是它的一个实现。 例4-4:selectKth的C语言递归实现 selectKth函数必须为数组A[left,right]选出pivotIndex来在递归中使用。如何选择这里存在

    • · 查看原书依据

      尾递归结构,一个非递归的实现会更直接一些。

    参考来源

    - 位置:《算法技术手册》第4章《使用环境》(spine1502;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1465.html;u074-ch04-013)。 - 结论依据:74全文和03198完整选择代码实读;重复键退化由分区条件推导,未运行程序。 - 原始内容:selectKth是一个平均时间为线性的函数,给定一个适当的pivotIndex,其返回了数组ar中的第k个元素,例4-4是它的一个实现。 例4-4:selectKth的C语言递归实现 selectKth函数必须为数组A[left,right]选出pivotIndex来在递归中使用。如何选择这里存在 - 位置:《算法技术手册》第4章《驱动因素》(spine1503;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1466.html;u075-ch04-013)。 - 结论依据:75指出可将尾递归改写为循环:每轮分区后更新 left、right 和必要时的 k,命中目标后返回索引。这样可避免递归栈增长,但不会消除重复键导致的分区退化。 - 原始内容:尾递归结构,一个非递归的实现会更直接一些。