2018-7-4
2.2.13 # 解答 # 假设对三个数进行排序，
这三个数是：35，10，17
三个数排序的决策树如下，
结点代表比较对应位置上的数。
对于 35,10,17 来说，路径遵循右、左、左，最后得到的结果就是 2 3 1（10,17,35）。
我们可以发现决策树上的每一个叶子节点都代表一种排列顺序，对于 N 个数，叶子节点就有 $N!$ 个
根据二叉树的性质，高度为 $h$ 的二叉树最多有 $2^h$ 个叶子节点
那么，对于 $N$ 个数，决策树的高度 $h$ 的最小值可以通过下面这个式子得出来
$2^h >= n!$
$h \ge log(n!)$
因此可以得到决策树高度 $h$ 的最小值是 $log(n!)$
接下来我们来计算平均路径长度
我们令函数 $H(k)$ 代表有 $k$ 个叶子节点的平衡决策树的所有路径长度之和
上例中 $H(6) = 2 + 2 + 3 + 3 + 3 + 3 = 16$
由于平衡决策树的性质，$H(k) = 2H(k / 2) + k$ （加上 $k$ 的原因：左右子树的高度比整个树的高度小 $1$，因此每条路径的长度都必须加 $1$，总共多加了 $k$ 次）
...
2018-7-4
2.2.14 # 解答 # 比较两个有序队列的第一个元素，取较小的一个出队并放入额外建立的队列中。
重复上述步骤直到两个队列都为空。
代码 # // 归并两个有序队列。输入队列将被清空。 static Queue<T> Merge<T>(Queue<T> a, Queue<T> b) where T : IComparable<T> { var sortedQueue = new Queue<T>(); while (!a.IsEmpty() && !b.IsEmpty()) { if (a.Peek().CompareTo(b.Peek()) < 0) sortedQueue.Enqueue(a.Dequeue()); else sortedQueue.Enqueue(b.Dequeue()); } while (!a.IsEmpty()) sortedQueue.Enqueue(a.Dequeue()); while (!b.IsEmpty()) sortedQueue.Enqueue(b.Dequeue()); return sortedQueue; }
2018-7-4
2.2.15 # 解答 # 程序思路题目已经给出，按照题意实现即可。
Merge 方法可以直接使用前一题的实现。
代码 # internal class MergeSortQueue { /// <summary> /// 利用队列归并进行自底向上的归并排序。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="array">需要排序的数组。</param> public void Sort<T>(T[] array) where T : IComparable<T> { var queueList = new Queue<Queue<T>>(); for (var i = 0; i < array.Length; i++) { var temp = new Queue<T>(); temp.Enqueue(array[i]); queueList.Enqueue(temp); } while (queueList.Size() != 1) { var times = queueList.Size() / 2; for (var i = 0; i < times; i++) { var a = queueList.
...
2018-7-4
2.2.16 # 解答 # 自然归并排序的一个示例如下图所示：
基本过程和自底向上的归并排序类似，只是每次归并的块大小不一定相同。
时间分析
随着有序块的变大，排序速度会加快，但增长的数量级也会变高（平均分块大小变大了）。
代码 # public class MergeSortNatural : BaseSort { /// <summary> /// 利用自然的归并排序进行自底向上的排序。 /// </summary> /// <typeparam name="T">用于排序的元素类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { var aux = new T[a.Length]; while (true) { // 找到第一个块 var lo = 0; var mid = FindBlock(lo, a) - 1; if (mid == a.Length - 1) break; while (mid < a.Length - 1) { var hi = FindBlock(mid + 1, a) + mid; Merge(lo, mid, hi, a, aux); lo = hi + 1; mid = FindBlock(lo, a) + lo - 1; } } Debug.
...
2018-7-4
2.2.17 # 解答 # 排序方式和 2.2.16 十分类似，不再赘述，这里介绍一下归并方法。
如 gif 图所示，先把要归并的两个链表拆出来，随后确定表头位置，然后进行归并即可。 归并结束后返回 first。
结果分析如下图所示：
随着有序部分的增加，对于相同大小的数组自然归并排序的耗时会缩短。
对于有序部分相同的情况，随着数组大小的倍增，耗时呈现了O(nlogn)的趋势。
代码 # public class MergeSortNatural : BaseSort { /// <summary> /// 利用自然的归并排序进行自底向上的排序。 /// </summary> /// <typeparam name="T">用于排序的元素类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { var aux = new T[a.Length]; while (true) { // 找到第一个块 var lo = 0; var mid = FindBlock(lo, a) - 1; if (mid == a.Length - 1) break; while (mid < a.
...
2018-7-4
2.2.18 # 解答 # 可以在用归并排序的方法做。
将归并时取两边较小的元素改为随机取一侧的值，即可实现打乱的效果。
算法的分析和普通归并排序一致，满足题目要求。
代码 # 分治法打乱链表的实现。
/// <summary> /// 分治法打乱链表。 /// </summary> public class MergeShuffle { /// <summary> /// 利用分治法打乱链表。 /// </summary> /// <typeparam name="T">链表元素类型。</typeparam> /// <param name="a">等待打乱的链表。</param> public void Shuffle<T>(LinkedList<T> a) { var blockLen = 1; var random = new Random(); while (blockLen <= a.Size()) { // 找到第一个块 var lo = a.GetFirst(); var mid = FindBlock(lo, blockLen); if (mid.Next == null) break; while (mid.Next !
...
2018-7-4
2.2.19 # 解答 # 官方实现：https://algs4.cs.princeton.edu/22mergesort/Inversions.java.html
事实上只要在归并排序的时候统计 Less(aux[j], aux[i]) 满足的次数即可，这个次数就是我们要的值。
代码 # /// <summary> /// 归并排序类。 /// </summary> public class MergeSort : BaseSort { public int Counter; /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { var aux = new T[a.Length]; Sort(a, aux, 0, a.Length - 1); } /// <summary> /// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T> { if (hi <= lo) return; var mid = lo + (hi - lo) / 2; Sort(a, aux, lo, mid); Sort(a, aux, mid + 1, hi); Merge(a, aux, lo, mid, hi); } /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">范围起点。</param> /// <param name="mid">范围中点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] a, T[] aux, int lo, int mid, int hi) where T : IComparable<T> { for (var k = lo; k <= hi; k++) { aux[k] = a[k]; } int i = lo, j = mid + 1; for (var k = lo; k <= hi; k++) { if (i > mid) { a[k] = aux[j]; j++; } else if (j > hi) { a[k] = aux[i]; i++; } else if (Less(aux[j], aux[i])) { a[k] = aux[j]; Counter += mid - i + 1; // 统计逆序对数 j++; } else { a[k] = aux[i]; i++; } } } } 另请参阅 # Merge 库
2018-7-4
2.2.20 # 解答 # 官方实现：https://algs4.cs.princeton.edu/22mergesort/Merge.java.html
把 Sort 方法中传入的 a 数组换成一个 index 数组，将 Merge 方法中的判断改为 Less(a[aux[j]], a[aux[i]]) 即可。
代码 # public class MergeSort : BaseSort { /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public int[] IndexSort<T>(T[] a) where T : IComparable<T> { var aux = new int[a.Length]; var index = new int[a.Length]; for (var i = 0; i < a.Length; i++) { index[i] = i; } Sort(a, index, aux, 0, a.
...
2018-7-4
2.2.21 # 解答 # 对三份列表进行归并排序（$O(nlogn)$），随后遍历一遍其中的一份表， 用二分查找检查在其余两个表中是否存在相同的姓名（$O(nlogn)$）。
代码 # var name1 = new[] { "Noah", "Liam", "Jacob", "Mason" }; var name2 = new[] { "Sophia", "Emma", "Mason", "Ava" }; var name3 = new[] { "Mason", "Marcus", "Alexander", "Ava" }; var mergeSort = new MergeSort(); mergeSort.Sort(name1); mergeSort.Sort(name2); mergeSort.Sort(name3); for (var i = 0; i < name1.Length; i++) { if (BinarySearch(name1[i], name2, 0, name1.Length) != -1 && BinarySearch(name1[i], name3, 0, name1.Length) != -1) { Console.
...
2018-7-4
2.2.22 # 解答 # 增长数量级为$O(nlogn)$。
代码 # /// <summary> /// 三向归并排序。 /// </summary> public class MergeSortThreeWay : BaseSort { /// <summary> /// 利用三项归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组中的元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { var aux = new T[a.Length]; Sort(a, aux, 0, a.Length - 1); Debug.Assert(IsSorted(a)); } /// <summary> /// 自顶向下地对数组指定范围内进行三向归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T> { if (hi <= lo) // 小于或等于一个元素 return; var lmid = lo + (hi - lo) / 3; var rmid = hi - (hi - lo) / 3; Sort(a, aux, lo, lmid); Sort(a, aux, lmid + 1, rmid); Sort(a, aux, rmid + 1, hi); Merge(a, aux, lo, lmid, rmid, hi); } /// <summary> /// 返回两个元素中较小的那个。 /// </summary> /// <typeparam name="T">比较的元素类型。</typeparam> /// <param name="a">用于比较的元素。</param> /// <param name="b">用于比较的元素。</param> /// <returns>较小的元素。</returns> private T Min<T>(T a, T b) where T : IComparable<T> { if (Less(a, b)) return a; return b; } /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">范围起点。</param> /// <param name="lmid">范围三分之一点。</param> /// <param name="rmid">范围三分之二点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] a, T[] aux, int lo, int lmid, int rmid, int hi) where T : IComparable<T> { for (var l = lo; l <= hi; l++) { aux[l] = a[l]; } int i = lo, j = lmid + 1, k = rmid + 1; for (var l = lo; l <= hi; l++) { var flag = 0; if (i > lmid) flag += 1; if (j > rmid) flag += 10; if (k > hi) flag += 100; switch (flag) { case 0: // 三个数组都还没有取完 var min = Min(aux[i], Min(aux[j], aux[k])); if (min.
...