知识卡片

普通读书笔记卡 · 3612.a.2

随机选择只递归目标侧

理解等级:中级

随机选择用随机枢轴分区,设枢轴在当前子数组中的秩为 k。

  • 目标秩 i=k 时直接返回;
  • i 时只处理左段;
  • i>k 时只处理右段且把目标秩改为 i−k。

与快排递归两侧不同,它每层只保留一个子问题。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 9 章 9.2 节(`OEBPS/chapter009.xhtml`,文本字符 [5000, 10000);图 9.1/Art_P340)。 - 结论依据:原文伪代码逐分支给出目标侧和秩次更新,图 9.1 展示逐轮缩小范围。 - 原始内容:R ANDOMIZED -S ELECT works on only one side of the partition.