知识卡片
快排先分区再处理两侧
快速排序先选枢轴值,把区间分成两侧,使左侧值不大于右侧范围,然后分别处理两边。它通过分区建立跨区间的相对关系,不像归并那样还需将两个有序结果逐项合并。
划分是否平衡决定递归形状:每次近乎对半时,各层线性扫描累计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。这是为什么?在实践中