知识卡片

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

中值排序以选择换取平衡

理解等级:中级

在闭区间内选择按秩位于中间的元素,将它放到中间位置,再交换两侧不符合中值分界的元素,递归排序两边。图示选择和分区使子数组大小大致均衡;重复值需按秩和一致的比较约定处理。

平衡递归本身不保证总耗时为 O(n log n):每层还要计入选择中值的代价。若每个子问题能在线性时间选择并分区,则总时间为 O(n log n)。

76中C实现以子区间长度的一半作为相对秩调用selectKth,随后递归处理两侧;选择完成时分界已建立。示例保存了返回索引me但没有再用它,递归边界直接从left与mid计算;正确性依赖selectKth确实把目标秩放到该位置。

77指出精确寻找中值有额外开销;随机选枢轴的快速排序可避免每次求精确中值,但随机化不能保证每次平衡,也不能单独排除重复键造成的退化。

78称平均 O(n log n) 与最坏 O(n²);需要区分一次partition的线性扫描与selectKth多轮最坏二次。精确中值排序若每次选择最坏线性则整体最坏 O(n log n),而书中给出的四元组代码及等值分区不足以直接支持这一结论。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      中值排序 在计算机科学中,分治是一种非常常见的方法,它将一个问题分成两个独立的子问题,每个子问题的规模是原始问题规模的一半。下面让我们来看看中值排序(图4-8),在对一个包含有n≥1个元素的数组A排序时,它交换中值元素A[me]和A的中位元素(第2~4行),将数组分成左右各一半。中值排序然后将左边大

    • · 查看原书依据

      不需要执行中值排序算法的第5~8行代码(图4-8),因为切分已经完成了。也就是说,左半部的元素都是小于或者等于中值的,反之,右半部的元素都是大于等于中值的。 例4-5的中值排序函数将要对A[0,n-1]进行排序。 例4-5:中值排序的C语言实现

    • · 查看原书依据

      额外开销应该考虑。在“快速排序”一节中,我们将会看到,随机地选择pivotIndex就足够了,这样就能够避免退化的情况(如果原始数组是有序的,这种情况很可能会发生)。

    • · 查看原书依据

      平均性能是O(n log n)。但是,在最坏情况下,partition函数执行时间为O(n2),这样就使得中值排序的性能退化到O(n2)。因此,当n个元素几乎有序的时候,即使待递归排序的子问题是非常理想化的,总体性能也会受到影响。我们在中值排序中使用一个随机化的select Pivot Index函

    参考来源

    - 位置:《算法技术手册》第4章《中值排序》(spine1502;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1465.html;u073-ch04-011)。 - 结论依据:73全文、03193伪代码和03194各递归阶段实读。 - 原始内容:中值排序 在计算机科学中,分治是一种非常常见的方法,它将一个问题分成两个独立的子问题,每个子问题的规模是原始问题规模的一半。下面让我们来看看中值排序(图4-8),在对一个包含有n≥1个元素的数组A排序时,它交换中值元素A[me]和A的中位元素(第2~4行),将数组分成左右各一半。中值排序然后将左边大 - 位置:《算法技术手册》第4章《解决方案》(spine1504;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1467.html;u076-ch04-011)。 - 结论依据:76中C实现以子区间长度的一半作为相对秩调用selectKth,随后递归处理两侧;选择完成时分界已建立。示例保存了返回索引me但没有再用它,递归边界直接从left与mid计算;正确性依赖selectKth确实把目标秩放到该位置。 - 原始内容:不需要执行中值排序算法的第5~8行代码(图4-8),因为切分已经完成了。也就是说,左半部的元素都是小于或者等于中值的,反之,右半部的元素都是大于等于中值的。 例4-5的中值排序函数将要对A[0,n-1]进行排序。 例4-5:中值排序的C语言实现 - 位置:《算法技术手册》第4章《结论》(spine1505;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1468.html;u077-ch04-011)。 - 结论依据:77指出精确寻找中值有额外开销;随机选枢轴的快速排序可避免每次求精确中值,但随机化不能保证每次平衡,也不能单独排除重复键造成的退化。 - 原始内容:额外开销应该考虑。在“快速排序”一节中,我们将会看到,随机地选择pivotIndex就足够了,这样就能够避免退化的情况(如果原始数组是有序的,这种情况很可能会发生)。 - 位置:《算法技术手册》第4章《分析》(spine1506;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1469.html;u078-ch04-011)。 - 结论依据:78称平均 O(n log n) 与最坏 O(n²);需要区分一次partition的线性扫描与selectKth多轮最坏二次。精确中值排序若每次选择最坏线性则整体最坏 O(n log n),而书中给出的四元组代码及等值分区不足以直接支持这一结论。 - 原始内容:平均性能是O(n log n)。但是,在最坏情况下,partition函数执行时间为O(n2),这样就使得中值排序的性能退化到O(n2)。因此,当n个元素几乎有序的时候,即使待递归排序的子问题是非常理想化的,总体性能也会受到影响。我们在中值排序中使用一个随机化的select Pivot Index函