知识卡片
分区将中枢放入最终秩
实现先把中枢交换到右端,扫描其余元素,将小于等于中枢者移到左侧,最后把中枢放到 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,返回值