知识卡片

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

分区将中枢放入最终秩

理解等级:中级

实现先把中枢交换到右端,扫描其余元素,将小于等于中枢者移到左侧,最后把中枢放到 store。返回 p 后,[left,p) 的元素均小于等于中枢,(p,right] 均严格大于中枢。分区只保证局部分界,并不保证两侧各自有序。

图中 pivot=6、p=5;若需要升序第八个元素,目标仍在右边,变成该右子区间的第2个。书中将其称作第八大,但该比较方向和示例对应第八小。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      partition(left,right,pivotIndex),这个函数将元素A[pivotIndex]作为一个特殊的中枢值,其将数组A[left,right]分成两半,其中一半中所有元素都小于等于中值元素,另一半的所有元素都大于等于中值元素。注意left≤pivotIndex≤right,返回值

    参考来源

    - 位置:《算法技术手册》第4章《使用环境》(spine1502;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1465.html;u074-ch04-012)。 - 结论依据:74全文、03195–03197代码与示例完整实读。 - 原始内容:partition(left,right,pivotIndex),这个函数将元素A[pivotIndex]作为一个特殊的中枢值,其将数组A[left,right]分成两半,其中一半中所有元素都小于等于中值元素,另一半的所有元素都大于等于中值元素。注意left≤pivotIndex≤right,返回值