知识卡片

问题卡 · 5654.c.1.a.2.a.7 · 生成模型:未记录

分区边界必须严格缩小递归

理解等级:中级

递归快排的每次调用必须让子区间严格小于原区间。分区返回的是左右界线,不一定是枢轴对象最终下标,递归端点须与分区规则配套。

本书partition从两端扫描,i>=k时返回k;qksort再递归左闭区间[原i,j]。若两项升序[1,2]恰取末项2作枢轴,扫描会在i=k=1停止并返回j=1,于是左递归仍是[0,1],这一步没有缩小。该采样可能发生,例如三次都选下标1。

下一次随机选择可能使其继续,但不能因此证明每步递归都减少规模或原宣称成本界已成立。修正需重新统一枢轴/分区不变量和端点,保证非平凡区间返回满足严格缩小条件;不能仅随意把某边减一而漏排元素。本卡给出未执行的逻辑反例,不声称已修复或测试。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      从i到j)。左边的分区继续递归,直到传入qksort的一个分区只包含单个元素。此时i不会比k小,所以递归调用终止。同样,分区的右边也在进行递归处理,处理的区间从j+1至k。总的来说,以这种递归方式继续运行,直到首次达到qksort终止的条件,此时,数据就完全排好序了(见图12-3)。 图 12-3

    参考来源

    - 位置:《算法精解:C语言描述》第12章《快速排序的实现与分析》(spine1342;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1308.html;u210-ch12-008)。 - 结论依据:210递归区间说明与02955–02956完整partition do扫描、break返回k及qksort左递归代码逐项实读,二元素反例按合法采样直接推导。 - 原始内容:从i到j)。左边的分区继续递归,直到传入qksort的一个分区只包含单个元素。此时i不会比k小,所以递归调用终止。同样,分区的右边也在进行递归处理,处理的区间从j+1至k。总的来说,以这种递归方式继续运行,直到首次达到qksort终止的条件,此时,数据就完全排好序了(见图12-3)。 图 12-3