知识卡片

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

快排先分区再处理两侧

理解等级:中级

快速排序先选枢轴值,把区间分成两侧,使左侧值不大于右侧范围,然后分别处理两边。它通过分区建立跨区间的相对关系,不像归并那样还需将两个有序结果逐项合并。

划分是否平衡决定递归形状:每次近乎对半时,各层线性扫描累计O(n log n);反复形成极小一边和大一边会累计到O(n²)。这些是机制模型,不能由“使用分治”单独推出对数层数。

随机枢轴降低固定坏输入持续造成极不平衡的风险,但不会把最坏情况确定改成平均情况。三样本中位数也不保证每次得到全数组中位数。原书“改进最坏与平均相当”“平衡将有保障”均需按期望分析而非确定承诺理解。

210的02953示例用28分区,[24,52,11,94,28,36,14,80]经交换52/14、94/28后分为[24,14,11,28]与[94,36,52,80];02954再按理想分区递归得到[11,14,24,28,36,52,80,94]。这是图例,不代表原代码已实际运行得到结果。

225一万条航班记录使用快排是书中建议,不凭条数就证明普遍最好;记录宽度/比较成本/稳定需求与底层已知错误仍需计入。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      分割值并将数据分为两部分。 2.治:分别在两部分用递归的方式继续使用快速排序法。 3.合:对分割部分排序直至完成。 令人惊讶的是,考虑到其流行程度,快速排序最坏情况下的性能不会比插入排序的最坏情况好。而事实上,通过一点点修改,可以大大改善快速排序最坏情况的效率,使其表现得与其平均情况相当。怎样做到这

    • · 查看原书依据

      partition完成(见示例12-2)。函数分割data中处于i和k之间的元素(其中i小于k)。 首先用之前提到过的中位数法选取一个分割值。一旦选定分割值,就将k往data的左边移动,直到找到一个小于或等于分割值的元素。这个元素属于左边分区。接下来,将i往右边移动,直到找到一个大于或等于分割值的元

    • · 查看原书依据

      10 000个C数据结构,它们包含一个航空公司的航班时刻表,我们需要此时刻表进行排序。这种情况下应该选择哪种排序算法? 答:快速排序。在一般情况下它是最好的排序算法,而且对于处理中到大型的数据非常高效。 问:回想一下,在接口qksort和mgsort中,需要函数调用者传入i和k。这是为什么?在实践中

    参考来源

    - 位置:《算法精解:C语言描述》第12章《快速排序的描述》(spine1340;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1306.html;u208-ch12-006)。 - 结论依据:208全部分治步骤、10/36分割例及随机/三样本说明实读,210完整平均/最坏讨论已读;随机期望边界沿已核验MIT随机快排讲义,不把统计保证变无最坏。 - 原始内容:分割值并将数据分为两部分。 2.治:分别在两部分用递归的方式继续使用快速排序法。 3.合:对分割部分排序直至完成。 令人惊讶的是,考虑到其流行程度,快速排序最坏情况下的性能不会比插入排序的最坏情况好。而事实上,通过一点点修改,可以大大改善快速排序最坏情况的效率,使其表现得与其平均情况相当。怎样做到这 - 位置:《算法精解:C语言描述》第12章《快速排序的实现与分析》(spine1342;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1308.html;u210-ch12-006)。 - 结论依据:210的02953示例用28分区,[24,52,11,94,28,36,14,80]经交换52/14、94/28后分为[24,14,11,28]与[94,36,52,80];02954再按理想分区递归得到[11,14,24,28,36,52,80,94]。这是图例,不代表原代码已实际运行得到结果。 - 原始内容:partition完成(见示例12-2)。函数分割data中处于i和k之间的元素(其中i小于k)。 首先用之前提到过的中位数法选取一个分割值。一旦选定分割值,就将k往data的左边移动,直到找到一个小于或等于分割值的元素。这个元素属于左边分区。接下来,将i往右边移动,直到找到一个大于或等于分割值的元 - 位置:《算法精解:C语言描述》第12章《问与答》(spine1357;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1323.html;u225-ch12-006)。 - 结论依据:225一万条航班记录使用快排是书中建议,不凭条数就证明普遍最好;记录宽度/比较成本/稳定需求与底层已知错误仍需计入。 - 原始内容:10 000个C数据结构,它们包含一个航空公司的航班时刻表,我们需要此时刻表进行排序。这种情况下应该选择哪种排序算法? 答:快速排序。在一般情况下它是最好的排序算法,而且对于处理中到大型的数据非常高效。 问:回想一下,在接口qksort和mgsort中,需要函数调用者传入i和k。这是为什么?在实践中