2018-7-14
2.3.14 # 解答 # 中文版题目有误，详见官方勘误页面
假设 $i < j$ 。
首先，在快速排序中，如果两个元素要发生交换，意味着其中一个元素被选为枢轴。
而且数组中的元素各不相同，那么两个特定的元素的比较最多发生一次。
那么先考虑一个特殊情况，$i = 1, j = n$ ，即求最大值和最小值比较的概率。
此时，一旦枢轴不是这两个元素之一，
最大值和最小值会被分到两个不同的子数组，无法发生比较。
因此在这种特例下第 $i$ 大的元素和第 $j$ 大的元素发生比较的概率为 $\frac{2}{n} = \frac{2}{j-i+1}$ 。
接下来考虑一般情况，如果枢轴选择了第 $i$ 到第 $j$ 大之外的元素，
那么第 $i$ 大和第 $j$ 大的元素会被分到同一个子数组里，重复上述过程。
因此我们所求的概率只和从第 $i$ 大到第 $j$ 大之间的元素有关，概率为 $\frac{2}{j-i+1}$。
（举个例子，一个箱子里有 2 个红球、1 个蓝球和 7 个白球，现在摸球而不放回。
如果摸到白球可以再摸一次，直到摸到红球或蓝球为止。
显然在这样的规则下摸到红球或蓝球的概率为 1，即白球对概率没有影响。）
现在我们已经得到了某两个元素比较的概率 $E(X_{ij})$，接下来我们求每两个元素比较的概率 $E(X)$。
$$ \begin{align} E(X) &= \sum_{i=1}^{n}\sum_{j=i+1}^{n}E(X_{ij})\newline &=\sum_{i=1}^{n}2(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n-i+1}) \newline &<2n(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}) \end{align} $$
根据调和级数的性质（$\ln (n) < 1+ \frac{1}{2}+ \cdots + \frac{1}{n} < 1+\ln(n)$），可以得到结论：
...
2018-7-15
2.3.15 # 解答 # 事实上只需要修改快速排序的切分方法，分两次进行切分。
首先选第一个螺母作为枢轴，找到对应的螺丝（$O(n)$）放到第一位，对螺丝数组进行切分。
然后再用找到的螺丝对螺母数组进行切分。
螺母类，实现了对螺丝类的 IComparable 接口
public class Nut<T> : IComparable<Bolt<T>> where T : IComparable<T> { /// <summary> /// 螺母的值。 /// </summary> public T Value { get; set; } /// <summary> /// 螺母的构造函数。 /// </summary> /// <param name="value">螺母的值。</param> public Nut(T value) => Value = value; /// <summary> /// 比较方法，螺母只能和螺丝比较。 /// </summary> /// <param name="other">需要比较的螺丝。</param> /// <returns></returns> public int CompareTo(Bolt<T> other) { return Value.CompareTo(other.Value); } } 类似的有螺丝类。
...
2018-7-19
2.3.16 # 解答 # 官方实现见：https://algs4.cs.princeton.edu/23quicksort/QuickBest.java.html
类似于快速排序的结构，只要中点的两边都是最佳情况，那么整个数组就是最佳情况了。
具体方法是：
首先构造一个有序数组，
然后找到中点（作为枢轴），
对中点左右两侧子数组进行构造，
将选择的枢轴放到开始处(a[lo])。
代码 # 用于构造最佳数组的类。
public class QuickBest { /// <summary> /// 构造函数，这个类不应该被实例化。 /// </summary> private QuickBest() { } /// <summary> /// 构造适用于快速排序的最佳数组。 /// </summary> /// <param name="n">数组长度。</param> /// <returns>适用于快速排序的最佳情况数组。</returns> public static int[] Best(int n) { var a = new int[n]; for (var i = 0; i < n; i++) { a[i] = i; } Best(a, 0, n - 1); return a; } /// <summary> /// 递归的构造数组。 /// </summary> /// <param name="a">需要构造的数组。</param> /// <param name="lo">构造的起始下标。</param> /// <param name="hi">构造的终止下标。</param> private static void Best(int[] a, int lo, int hi) { if (hi <= lo) return; var mid = lo + (hi - lo) / 2; Best(a, lo, mid - 1); Best(a, mid + 1, hi); Exch(a, lo, mid); } /// <summary> /// 交换数组中的两个元素。 /// </summary> /// <param name="a">包含要交换元素的数组。</param> /// <param name="x">需要交换的第一个元素下标。</param> /// <param name="y">需要交换的第二个元素下标。</param> private static void Exch(int[] a, int x, int y) { var t = a[x]; a[x] = a[y]; a[y] = t; } } 用于测试的方法
...
2018-7-22
2.3.17 # 解答 # 按照题意修改代码即可，在调用 Suffle() 之后添加一段用于寻找最大值的方法（$O(n)$）。
public override void Sort<T>(T[] a) { Shuffle(a); // 把最大元素放到最后一位 var maxIndex = 0; for (var i = 0; i < a.Length; i++) { if (Less(a[maxIndex], a[i])) maxIndex = i; } Exch(a, maxIndex, a.Length - 1); Sort(a, 0, a.Length - 1); Debug.Assert(IsSorted(a)); } 代码 # 修改后的快速排序类。
public class QuickSortX : BaseSort { /// <summary> /// 用快速排序对数组 a 进行升序排序。 /// </summary> /// <typeparam name="T">需要排序的类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { Shuffle(a); // 把最大元素放到最后一位 var maxIndex = 0; for (var i = 0; i < a.
...
2018-7-24
2.3.18 # 解答 # 每次切分时都取前三个元素的中位数作为枢轴，这可以带来约 5%~10% 的性能提升。
这里通过三次比较将前三个数排序，然后把三个数中的中位数放到数组开头，最大值放到数组末尾。
最大值被放到了末尾，枢轴不可能大于末尾的这个数，因此右边界判断可以去掉。
同时由于枢轴不可能小于自身，因此左边界判断也可以去掉。
这样就可以把切分中的两个边界判断全部去掉了。
最后对于大小为 2 的数组做特殊处理，通过一次比较直接排序并返回。
测试结果：
代码 # QuickSortMedian3 # public class QuickSortMedian3 : BaseSort { /// <summary> /// 用快速排序对数组 a 进行升序排序。 /// </summary> /// <typeparam name="T">需要排序的类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { Shuffle(a); Sort(a, 0, a.Length - 1); Debug.Assert(IsSorted(a)); } /// <summary> /// 用快速排序对数组 a 的 lo ~ hi 范围排序。 /// </summary> /// <typeparam name="T">需要排序的数组类型。</typeparam> /// <param name="a">需要排序的数组。</param> /// <param name="lo">排序范围的起始下标。</param> /// <param name="hi">排序范围的结束下标。</param> private void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T> { if (hi <= lo) // 别越界 return; // 只有两个元素的数组直接排序 if (hi == lo + 1) { if (Less(a[hi], a[lo])) Exch(a, lo, hi); return; } var j = Partition(a, lo, hi); Sort(a, lo, j - 1); Sort(a, j + 1, hi); } /// <summary> /// 对数组进行切分，返回枢轴位置。 /// </summary> /// <typeparam name="T">需要切分的数组类型。</typeparam> /// <param name="a">需要切分的数组。</param> /// <param name="lo">切分的起始点。</param> /// <param name="hi">切分的末尾点。</param> /// <returns>枢轴下标。</returns> private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T> { int i = lo, j = hi + 1; if (Less(a[lo + 1], a[lo])) Exch(a, lo + 1, lo); if (Less(a[lo + 2], a[lo])) Exch(a, lo + 2, lo); if (Less(a[lo + 2], a[lo + 1])) Exch(a, lo + 1, lo + 2); Exch(a, lo, lo + 1); // 中位数放最左侧 Exch(a, hi, lo + 2); // 较大的值放最右侧作为哨兵 var v = a[lo]; while (true) { while (Less(a[++i], v)) { } while (Less(v, a[--j])) { } if (i >= j) break; Exch(a, i, j); } Exch(a, lo, j); return j; } /// <summary> /// 打乱数组。 /// </summary> /// <typeparam name="T">需要打乱的数组类型。</typeparam> /// <param name="a">需要打乱的数组。</param> private void Shuffle<T>(T[] a) { var random = new Random(); for (var i = 0; i < a.
...
2018-7-28
2.3.19 # 解答 # 主要介绍一下这个少于七次比较的五取样算法。
首先假设五个数字为 a b c d e
对 b c 排序，d e 排序。（两次比较）
比较 b 和 d，把较小那一组换到 b c 的位置上去。（一次比较）
此时会有 b < c, b < d < e。
交换 a, b，重新对 b c 排序。（一次比较）
再次比较 b 和 d，把较小的那一组换到 b c 的位置上。（一次比较）
最后比较 c 和 d，较小的那一个即为中位数。（一次比较）
总共需要 6 次比较，严格小于 7 次。
取样完毕后，a b 是最小值和次小值（这里没有对应关系，a 也可以是次小值）。
d 和 e 是最大值和次大值（同样没有对应关系）。
我们把 d 和 e 放到数组的最后作为哨兵，去掉右边界的判断。
同时让左右两侧指针都向中间移动两位，减少不必要的比较。
...
2018-7-29
2.3.20 # 解答 # 事实上就是用一个栈保存每次切分后的子数组下标。
关键代码如下：
/// <summary> /// 用快速排序对数组 a 进行升序排序。 /// </summary> /// <typeparam name="T">需要排序的类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { Shuffle(a); var stack = new Stack<int>(); stack.Push(0); stack.Push(a.Length - 1); while (stack.Count != 0) { // 压入顺序是先 lo，再 hi，故弹出顺序是先 hi 再 lo var hi = stack.Pop(); var lo = stack.Pop(); if (hi <= lo) continue; var j = Partition(a, lo, hi); // 让较大的子数组先入栈（先排序较小的子数组） if (j - lo > hi - j) { stack.
...
2018-7-31
2.3.21 # 解答 # 首先引入命题 I 的结论，对于互不相同的主键值，基于比较的排序算法的下界等于所形成的比较树的高度，即：
$$ h \ge \log_2{N!} $$
那么我们题目即可转化为求证
$$ h \ge \log_2 (\frac{N!}{f_1!f_2!\cdots f_k!}) \ge \log_2 N! $$
这里的 $f_i$ 为某个主键值出现的频率，即某个主键值出现的次数，因此 $f_i\ge 1$ 。
根据题目给出的条件，如果主键互不重复，此时 $k=N$，且 $f_1=f_2=\cdots=f_k=1$ 。
那么 $f_1!f_2!\cdots f_k!=1$ ，待证式子即为命题 I 的结论。
那么当主键有重复时，此时 $k < N$，为使 $f_1+f_2+ \cdots + f_k=N$ ，至少存在一个 $f_m \ge 2$。
故此时：
$$ f_1!f_2!\cdots f_k! >1\Rightarrow \frac{N!}{f_1!f_2!\cdots f_k!}<N! \Rightarrow \newline h \ge \log_2 (\frac{N!}{f_1!f_2!\cdots f_k!}) \ge \log_2 N! \ \blacksquare $$
...
2018-8-2
2.3.22 # 解答 # 官方实现见：https://algs4.cs.princeton.edu/23quicksort/QuickBentleyMcIlroy.java.html
快速三向切分 # 论文引用见「另请参阅」部分。
算法演示
Ninther 算法 # 官方实现中用到了 Ninther 算法用于选取近似中位数（作为枢轴），
该算法由 John Tukey 在 1978 年提出，论文引用见「另请参阅」部分。
这个算法的思想其实很简单，假设我们有三个数 $y_1, y_2, y_3$ ，那么其中位数为：
$$ y_A= {\rm median}\lbrace y_1,y_2,y_3 \rbrace $$
现在对于九个数，我们以三个为一组，取三个中位数：
$$ y_A= {\rm median}\lbrace y_1,y_2,y_3 \rbrace \newline y_B= {\rm median}\lbrace y_4,y_5,y_6 \rbrace \newline y_C= {\rm median}\lbrace y_7,y_8,y_9 \rbrace $$
接下来取这三个中位数的中位数，有：
$$ y_E= {\rm median}\lbrace y_A,y_B,y_C \rbrace $$
我们把上述过程封装成函数，即 $y_E= {\rm ninther}\lbrace y_1,y_2,\cdots,y_9 \rbrace$ 。
于是我们获得的 $y_E$ 即为近似中位数，如果 $\lbrace y_1,y_2,\cdots,y_9 \rbrace$ 是单调数列，那么 $y_E$ 就是中位数。
...
2018-8-4
2.3.23 # 解答 # 官方实现见：https://algs4.cs.princeton.edu/23quicksort/QuickBentleyMcIlroy.java.html
见 2.3.22 的解答，其中已经包含了这些改动。
代码 # QuickBentleyMcIlroy
public class QuickBentleyMcIlroy : BaseSort { /// <summary> /// 小于这个数值的数组调用插入排序。 /// </summary> private readonly int _insertionSortCutoff = 8; /// <summary> /// 小于这个数值的数组调用中位数作为枢轴。 /// </summary> private readonly int _medianOf3Cutoff = 40; /// <summary> /// 用快速排序对数组 a 进行升序排序。 /// </summary> /// <typeparam name="T">需要排序的类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { Sort(a, 0, a.Length - 1); Debug.Assert(IsSorted(a)); } /// <summary> /// 对指定范围内的数组进行排序。 /// </summary> /// <typeparam name="T">需要排序的类型。</typeparam> /// <param name="a">需要排序的数组。</param> /// <param name="lo">排序的起始下标。</param> /// <param name="hi">排序的终止下标。</param> private void Sort<T>(T[] a, int lo, int hi) where T : IComparable<T> { var n = hi - lo + 1; if (n <= _insertionSortCutoff) { InsertionSort(a, lo, hi); return; } if (n <= _medianOf3Cutoff) { // 对于较小的数组，直接选择左中右三个元素中的中位数作为枢轴。 var m = Median3(a, lo, lo + n / 2, hi); Exch(a, m, lo); } else { // 对于较大的数组使用 Turkey Ninther 作为枢轴。 var eps = n / 8; var mid = lo + n / 2; var m1 = Median3(a, lo, lo + eps, lo + eps + eps); var m2 = Median3(a, mid - eps, mid, mid + eps); var m3 = Median3(a, hi - eps - eps, hi - eps, hi); var ninther = Median3(a, m1, m2, m3); Exch(a, ninther, lo); } // 三向切分 int i = lo, j = hi + 1; int p = lo, q = hi + 1; var v = a[lo]; while (true) { while (Less(a[++i], v)) { } while (Less(v, a[--j])) if (j == lo) break; if (i == j && IsEqual(a[i], v)) Exch(a, ++p, i); if (i >= j) break; Exch(a, i, j); if (IsEqual(a[i], v)) Exch(a, ++p, i); if (IsEqual(a[j], v)) Exch(a, --q, j); } i = j + 1; for (var k = lo; k <= p; k++) Exch(a, k, j--); for (var k = hi; k >= q; k--) Exch(a, k, i++); Sort(a, lo, j); Sort(a, i, hi); } /// <summary> /// 判断两个元素是否值相等。 /// </summary> /// <typeparam name="T">需要判断的元素类型。</typeparam> /// <param name="a">进行比较的第一个元素。</param> /// <param name="b">进行比较的第二个元素。</param> /// <returns>两个元素的值是否相等。</returns> private bool IsEqual<T>(T a, T b) where T : IComparable<T> { return a.
...