2.3.4 # 解答 # 每次只让枢轴变为已排序，这就是最坏情况。 这种时候枢轴是当前子数组的最大值 / 最小值。 由于在我们的实现中总是取子数组的第一个元素作为枢轴。 因此一个已排序的数组可以达到最坏情况，比较次数达到 O(n^ 2)。 如果换作取最后一个元素，最坏情况会变成逆序数组。 我们的实现中如果碰到与枢轴相等的元素也会停止循环， 因此如果数组中有重复的元素会减少比较次数。 例如： 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11 12 4 5 6 7 8 9 10 11 12 13 5 6 7 8 9 10 11 12 13 14 6 7 8 9 10 11 12 13 14 15 另请参阅 # Analysis of Quicksort-khanacademy Worst case for QuickSort - When can it occur? ...
2.3.5 # 解答 # 官方实现：https://algs4.cs.princeton.edu/23quicksort/Sort2distinct.java.html 算法 gif 动图 代码 # public class Sort2Distinct : BaseSort { /// <summary> /// 对数组 a 进行排序。 /// </summary> /// <typeparam name="T">数组 a 的元素类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { int lt = 0, gt = a.Length - 1; var i = 0; while (i <= gt) { var cmp = a[i].CompareTo(a[lt]); if (cmp < 0) Exch(a, lt++, i++); else if (cmp > 0) Exch(a, i, gt--); else i++; } } } 另请参阅 # Quick 库
2.3.6 # 解答 # 运行结果如下： 代码 # 新建一个 QuickSortAnalyze 类，在 QuickSort 的基础上添加一个 CompareCount 属性，用于记录比较次数。重写 Less 方法，每调用一次就让 CompareCount 增加 1 。 /// <summary> /// 自动记录比较次数以及子数组数量的快速排序类。 /// </summary> public class QuickSortAnalyze : BaseSort { /// <summary> /// 比较次数。 /// </summary> /// <value>排序用的比较次数。</value> public int CompareCount { get; set; } /// <summary> /// 是否启用打乱。 /// </summary> /// <value> /// <list type="bullet"> /// <item><c>true</c>: 启用排序前打乱。</item> /// <item><c>false</c>: 禁用排序前打乱。</item> /// </list> /// </value> public bool NeedShuffle { get; set; } /// <summary> /// 是否显示轨迹。 /// </summary> /// <value> /// <list type="bullet"> /// <item><c>true</c>: 输出排序轨迹。</item> /// <item><c>false</c>: 不输出排序轨迹。</item> /// </list> /// </value> public bool NeedPath { get; set; } /// <summary> /// 大小为 0 的子数组数量。 /// </summary> /// <value>大小为 0 的子数组数量。</value> public int Array0Num { get; set; } /// <summary> /// 大小为 1 的子数组数量。 /// </summary> /// <value>大小为 1 的子数组数量。</value> public int Array1Num { get; set; } /// <summary> /// 大小为 2 的子数组数量。 /// </summary> /// <value>大小为 2 的子数组数量。</value> public int Array2Num { get; set; } /// <summary> /// 默认构造函数。 /// </summary> public QuickSortAnalyze() { CompareCount = 0; NeedShuffle = true; NeedPath = false; Array0Num = 0; Array1Num = 0; Array2Num = 0; } /// <summary> /// 用快速排序对数组 a 进行升序排序。 /// </summary> /// <typeparam name="T">需要排序的类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { Array0Num = 0; Array1Num = 0; Array2Num = 0; CompareCount = 0; if (NeedShuffle) Shuffle(a); if (NeedPath) { for (var i = 0; i < a. ...
2.3.7 # 解答 # 我讨厌数学= = 证明： 我们设 $C_0(n)$ 代表将 $n$ 个不重复元素排序时大小为 0 的数组的数量。 同理有 $C_1(n)$ 和 $C_2(n)$ 代表大小为 1 的数组的数量以及大小为 2 的数组的数量。 设 k 代表切分位置，显然切分位置随机且概率相等，在 1~n 之间均匀分布。 根据条件，$C_0(n), C_1(n),C_2(n)$ 都满足下式： $$ C(n)= \frac{\sum_{k=1}^{n}(C(k-1)+C(n-k))}{n} $$ 根据快速排序算法， $\sum_{k=1}^{n}C(k-1)=\sum_{k=1}^{n}C(n-k)$ ，因此 $$ C(n)=\frac{2\sum_{k=1}^{n}C(k-1)}{n}\newline nC(n)=2\sum_{k-1}^{n}C(k-1) $$ 同理代入 $n-1$ 有 $$ (n-1)C(n-1)=2\sum_{k-1}^{n-1}C(k-1) $$ 相减 $$ nC(n)-(n-1)C(n-1)=2C(n-1)\newline C(n)=\frac{n+1}{n}C(n-1) $$ 利用累乘法求到通项公式 $$ \frac{C(n)}{C(n-1)}=\frac{n+1}{n} \newline \frac{C(n)}{C(n-1)}\times\frac{C(n-1)}{C(n-2)}\times\dots\times\frac{C(m+1)}{C(m)}= \frac{n+1}{n}\times\frac{n}{n-1}\times\dots\times\frac{m+2}{m+1}\newline \frac{C(n)}{C(m)}=\frac{n+1}{m+1}\newline C(n)=C(m)\frac{n+1}{m+1}，n>m $$ 对于 $C_0(n)$ ，我们有初始条件 $C_0(0)=1, C_0(1)=0,C_0(2)=C_0(0)+C_0(1)=1$ $$ C_0(n)=\frac{n+1}{3}, n>2 $$ ...
2.3.8 # 解答 # 每次切分都会把数组平分，共切分 logN 次（二分法），每次切分比较 N 次（i 和 j 会一位一位地从两边向中间靠拢）。 共比较 NlogN 次。
2.3.9 # 解答 # 切分时，枢轴左侧都是小于（或等于）枢轴的， 右侧都是大于（或等于）枢轴的 只有两种主键值时， 第一次切分之后，某一侧的元素将全部相同 （如果枢轴选了较大的，那么右侧将全部相同，反之则左侧全部相同） 只有三种主键值时，和一般快速排序并无不同。 但如果第一次切分时选择了中间值作为枢轴，且中间值只有一个 那么只需要一次切分数组便会有序。
2.3.10 # 解答 # 切比雪夫不等式（Chebyshev’s inequality） $$ P(|X-\mu|\geq k\sigma)\leq \frac{1}{k^2} $$ 其中，$\mu$ 代表期望，$\sigma$ 代表标准差。 对于快速排序的比较次数来说，$\mu = 2N\ln N$ ，$\sigma=0.65N$。 （这两个结论见 2.3 节的命题 K 和命题 L） 题目中要求比较次数大于 $0.1N^2$ ，可以求得 $k$ 的值。 $$ 0.65kN=0.1N^2 \newline k=\frac{2N}{13} $$ 将 $N=1,000,000$ 代入 $$ P(|X-27,631,021|\geq 100,000,000,000)\leq 0.00000000004225 $$ 另请参阅 # 切比雪夫不等式到底是个什么概念? - 马同学的回答 - 知乎
2.3.11 # 解答 # 只有若干种元素值意味着大量的连续重复。 （由于存在打乱这一步骤，不存在连续重复的可能性是很低的） 接下来我们考虑这样的连续重复在修改后的快排下的性能。 1 1 1 1 1 1 1 对于这样的数组，枢轴选为 1，j 将会在 j = lo 处终止。 因此最后的结果将是每次只有数组的第一个元素被排序 已知每次切分都是 O(k - 1) 的（i 和 j 都将走完整个子数组） 因此这样的快速排序所需时间 = $2 (N - 1 + N - 2 + \cdots + 1) = (N - 1)N$ 因此对于值相同的子数组，这样的快排运行时间是平方级别的 那么当数组中这样的连续重复内容越多，运行时间就越接近平方级别。
2.3.12 # 解答 #
2.3.13 # 解答 # 快速排序先将数组分为 （小于枢轴）枢轴（大于枢轴）三部分，然后再分别递归的排序左右两部分数组。 在这里，我们可以将快速排序的递归树看作是一棵二叉搜索树（BST, Binary Search Tree）。 枢轴作为根结点，左子树即为左数组构造的 BST，右子树即为右数组构造的 BST。 这样题目中所求的递归深度即为所构造的 BST 的高度。 最坏情况，每次都只有枢轴和大于枢轴两部分，BST 退化为链表，高度为 $n-1$。 最好情况，每次枢轴都正好平分数组，构造一棵完全二叉树，高度为 $\log n$。 平均情况，问题转化为：一个由 $n$ 个元素随机构造的 BST 的平均高度是多少？ 《算法导论》给出的结论是 $\log n$ ，具体证明如下： 设由 $n$ 个结点随机构成的 BST 的高度为 $h_n$，那么有： $$ h_n=1+\max(h_{l}+h_{r}) $$ 其中，$h_l$ 和 $h_r$ 分别代表左数组和右数组构造的 BST 的高度。 设枢轴位置为 $i$，上式可简化为： $$ h_n=1+\max(h_{i-1}, h_{n-i}) $$ 由于枢轴位置可以在 1~n 之间任意取值且概率相等，因此 BST 的平均高度（即高度的期望）为： $$ E(h_n)=\frac{1}{n}\sum_{i=1}^{n}\lbrack 1+\max(h_{i-1}, h_{n-i}) \rbrack $$ 我们令 $Y_n=2^{h_n}$，可得： $$ Y_n=2\times\max(Y_{i-1},Y_{n-i}) $$ 我们把 $Y_n$ 代入，可得： ...