知识卡片

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

快速排序递归处理分区

理解等级:中级

选择枢轴并将其放到最终位置;左侧不大于枢轴,右侧不小于枢轴,再独立排序两个子区间。具体不等号由分区实现决定,书中代码把等值放左侧。图中首次选2得到1和14个元素,另一次选择中值附近元素则较平衡。

均匀随机枢轴在互异键下有期望 O(n log n) 时间,最坏仍为 O(n²);分区质量和重复键处理决定实际性能。图中的原地交换一般不保持相等元素的原始顺序。

80指出一侧为空而另一侧只少一个元素时,递归总工作量为二次。选择多个样本的中位数可改善通常的分区质量,但增加采样成本,不能无条件保证最坏情况。

82强调实践中的快速排序及其优化;具体性能需要与数据结构、输入分布和替代算法在同一环境下比较,不能把书中历史结论视为对所有工作负载的保证。

83分析:若每次均等分区,线性分区成本加上两半递归得到 O(n log n);若持续只排定一个元素,递推 T(n)=T(n−1)+O(n) 得到 O(n²)。随机策略的期望复杂度与每次恰好平衡是不同命题。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      快速排序 如果我们仔细考虑中值排序的性能,我们会发现随机选择pivotIndex将仍使selectKth的性能为线性时间。我们可以简化算法但是不会引起额外的性能开销吗?在某些情况下,这种简化实现能够快些吗?C.A.R.Hoare发明的快速排序虽然使用了大致相同的思想(这就是为什么我们首先介绍中值排序

    • · 查看原书依据

      二次方行为。 在每一次切分后,中枢值的选择强烈地影响了两个子数组的大小。我们可以选择k(k为奇数)个随机元素的中值,而不是选择一个随机元素。在随后的“变种”一节中,我们将讨论不同的选择中枢值的策略。

    • · 查看原书依据

      优化和强化研究使得快速排序成为最为高效的算法。稍后我们将会在“变种”一节中讨论各种变种的细节。

    • · 查看原书依据

      t(n)=2*t(n/2)+O(n) O(n)表示切分数组需要花费线性时间。第2章已经介绍过,如果一个算法能够用这样的t(n)来定义行为,那么其性能为O(n log n)。从大量实践的经验上来看,因为被抽象成为O(n)的常数比较小,快速排序要比中值排序快。快速排序的总开销也比较少,因为它不需要在构建

    参考来源

    - 位置:《算法技术手册》第4章《快速排序》(spine1507;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1470.html;u079-ch04-015)。 - 结论依据:79全文、03206伪代码与03207–03208两次示例实读。 - 原始内容:快速排序 如果我们仔细考虑中值排序的性能,我们会发现随机选择pivotIndex将仍使selectKth的性能为线性时间。我们可以简化算法但是不会引起额外的性能开销吗?在某些情况下,这种简化实现能够快些吗?C.A.R.Hoare发明的快速排序虽然使用了大致相同的思想(这就是为什么我们首先介绍中值排序 - 位置:《算法技术手册》第4章《使用环境》(spine1507;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1470.html;u080-ch04-015)。 - 结论依据:80指出一侧为空而另一侧只少一个元素时,递归总工作量为二次。选择多个样本的中位数可改善通常的分区质量,但增加采样成本,不能无条件保证最坏情况。 - 原始内容:二次方行为。 在每一次切分后,中枢值的选择强烈地影响了两个子数组的大小。我们可以选择k(k为奇数)个随机元素的中值,而不是选择一个随机元素。在随后的“变种”一节中,我们将讨论不同的选择中枢值的策略。 - 位置:《算法技术手册》第4章《结论》(spine1509;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1472.html;u082-ch04-015)。 - 结论依据:82强调实践中的快速排序及其优化;具体性能需要与数据结构、输入分布和替代算法在同一环境下比较,不能把书中历史结论视为对所有工作负载的保证。 - 原始内容:优化和强化研究使得快速排序成为最为高效的算法。稍后我们将会在“变种”一节中讨论各种变种的细节。 - 位置:《算法技术手册》第4章《分析》(spine1510;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1473.html;u083-ch04-015)。 - 结论依据:83分析:若每次均等分区,线性分区成本加上两半递归得到 O(n log n);若持续只排定一个元素,递推 T(n)=T(n−1)+O(n) 得到 O(n²)。随机策略的期望复杂度与每次恰好平衡是不同命题。 - 原始内容:t(n)=2*t(n/2)+O(n) O(n)表示切分数组需要花费线性时间。第2章已经介绍过,如果一个算法能够用这样的t(n)来定义行为,那么其性能为O(n log n)。从大量实践的经验上来看,因为被抽象成为O(n)的常数比较小,快速排序要比中值排序快。快速排序的总开销也比较少,因为它不需要在构建