Sort

2.2.4

2018-7-4
Sort

2.2.4 # 解答 # 是的，必须要两个子数组都有序时归并才能得到正确结果。 如果说数组不有序的话，那么最后只能得到两个数组的混合。 合并后的数组中，属于原有数组的元素的相对顺序不会被改变。 例如子数组 1 3 1 和 2 8 5 原地归并。 结果是 1 2 3 1 8 5，其中 1 3 1 和 2 8 5 的相对顺序不变。

2.2.5

2018-7-4
Sort

2.2.5 # 解答 # 每次归并子数组的大小和顺序如下： 自顶向下 2, 3, 2, 5, 2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 3, 2, 5, 10, 20, 2, 3, 2, 5, 2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 2, 4, 9, 19, 39 自底向上 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 8, 8, 8, 8, 7, 16, 16, 32, 39

2.2.6

2018-7-4
Sort

2.2.6 # 解答 # 灰色是上限，蓝点是自顶向下，红点是自底向上。 由于两种排序访问数组的次数是一样的，因此蓝点和红点重合。 代码 # 给出绘图部分的代码： using System; using System.Windows.Forms; using System.Drawing; using Merge; namespace _2._2._6 { static class Program { /// <summary> /// 应用程序的主入口点。 /// </summary> [STAThread] static void Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Compute(); Application.Run(new Form1()); } static void Compute() { MergeSort mergeSort = new MergeSort(); MergeSortBU mergeSortBU = new MergeSortBU(); int[] mergeResult = new int[10]; int[] mergeResultBU = new int[10]; int[] upperBound = new int[10]; // 进行计算 int dataSize = 1; for (int i = 0; i < 10; i++) { int[] dataMerge = SortCompare. ...

2.2.7

2018-7-4
Sort

2.2.7 # 解答 # 根据书本给出的命题 G 和命题 H（中文版 P173/176，英文版 P275/279）， 比较次数的下限 $C(N) = 1/2 \times NlgN$ $N$ 和 $lgN$ 都是单调递增且大于零的($N>1$)， 因此 $C(N)$ 也是单调递增的。

2.2.8

2018-7-4
Sort

2.2.8 # 解答 # 修改后的算法对已经有序的情况做了优化 数组对半切分并排序后， 如果 a[mid] < a[mid + 1](左半部分的最后一个元素小于右半部分的第一个元素) 那么我们可以直接合并数组，不需要再做多余的操作 现在的输入是一个已经排序的数组 算法唯一的比较发生在判断 a[mid] < a[mid + 1] 这个条件时 假定数组有 $N$ 个元素 比较次数满足 $T(N) = 2 T(N / 2) + 1, T(1) = 0$ 转化为非递归形式即为：$T(N) = cN / 2 + N - 1$ 其中 $c$ 为任意正整数。

2.2.9

2018-7-4
Sort

2.2.9 # 解答 # 官方给出的归并排序实现中在 Sort 方法里初始化了 aux 数组。 源码见：https://algs4.cs.princeton.edu/22mergesort/Merge.java.html C#实现和官方的实现非常类似， 首先定义只接受一个参数的公开 Sort 方法，在这个方法里面初始化 aux 数组。 /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { T[] aux = new T[a.Length]; Sort(a, aux, 0, a.Length - 1); } 然后建立一个私有的递归 Sort 方法做实际的排序操作。 /// <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; int mid = lo + (hi - lo) / 2; Sort(a, aux, lo, mid); Sort(a, aux, mid + 1, hi); Merge(a, aux, lo, mid, hi); } 代码 # public class MergeSort : BaseSort { /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { var aux = new T[a. ...

2.2.10

2018-7-4
Sort

2.2.10 # 解答 # 官方同样给出了 java 实现，如下： private static void merge(Comparable[] a, int lo, int mid, int hi) { for (int i = lo; i <= mid; i++) aux[i] = a[i]; for (int j = mid+1; j <= hi; j++) aux[j] = a[hi-j+mid+1]; int i = lo, j = hi; for (int k = lo; k <= hi; k++) if (less(aux[j], aux[i])) a[k] = aux[j--]; else a[k] = aux[i++]; } C# 实现见代码部分。 ...

2.2.11

2018-7-4
Sort

2.2.11 # 解答 # 官方实现见：https://algs4.cs.princeton.edu/22mergesort/MergeX.java.html 在 MergeSortX 类里添加一个 CUTOFF 字段，排序时如果数组长度小于它则直接调用插入排序进行排序。 在调用归并方法前判断第一个有序数组的最后一个元素是否大于第二个有序数组的第一个元素， 如果大于的话就不需要调用归并了，直接首尾相接即可。 归并的空间优化类似于左手倒右手，从一个数组读数据写到另一个数组中去，下一次归并的时候就可以反过来操作，从而节省数组空间。 每次归并都需要两个数组，一个用于存放归并结果，这个数组中的内容是无关紧要的（Merge() 方法中的 dst 数组） 另一个则保存了归并前的数组，用于实际的归并过程（src 数组）。 归并结束后，前一个数组变成归并后的有序结果（也就是下一次归并时的「归并前数组」），后一个数组中的内容则不再有用。 我们可以看到这两个数组的角色在下一次归并时正好可以互换。 要注意的是，交换次数总是一个奇数（左侧排序+右侧排序+总归并），因此在第一次调用 Sort 方法时应该把 aux 和 a 互换传入。 代码 # public class MergeSortX : BaseSort { /// <summary> /// 对小于 CUTOFF 的数组使用插入排序。 /// </summary> private static int _cutoff = 7; /// <summary> /// 设置启用插入排序的阈值，小于该阈值的数组将采用插入排序。 /// </summary> /// <param name="cutoff">新的阈值。</param> public void SetCutOff(int cutoff) => _cutoff = cutoff; /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="src">原始数组。</param> /// <param name="dst">目标数组。</param> /// <param name="lo">范围起点。</param> /// <param name="mid">范围中点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] src, T[] dst, int lo, int mid, int hi) where T : IComparable<T> { int i = lo, j = mid + 1; for (var k = lo; k <= hi; k++) { if (i > mid) dst[k] = src[j++]; else if (j > hi) dst[k] = src[i++]; else if (Less(src[j], src[i])) dst[k] = src[j++]; else dst[k] = src[i++]; } } /// <summary> /// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="src">原数组。</param> /// <param name="dst">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] src, T[] dst, int lo, int hi) where T : IComparable<T> { // 小于 CUTOFF 的数组调用插入排序 if (hi <= lo + _cutoff) { var insertion = new InsertionSort(); insertion. ...

2.2.12

2018-7-4
Sort

2.2.12 # 解答 # 中文版的翻译比较难理解。 实际上就是另一种归并排序的实现方式。 先把数组分成若干个大小为 M 的块 。 对于每个块，用选择排序进行排序 。 随后遍历数组，将各个块归并起来。 归并时仅复制右侧数组就够了，然后倒着归并（从右到左），可以将额外空间降到 M。 具体归并流程如下： 复制右侧数组到 aux，现在右侧数组a[hi]~a[mid+1]中的元素可以被安全覆盖。 设定指针i,j,k，将数组 a[mid]~a[0] 和 aux[hi-mid-1]~aux[mid + 1] 归并到 a[hi - 1]~a[0]。 在这个流程中左侧数组的指针i是不会大于归并的写入指针k的。 最坏情况下，aux用尽时 i == k，左侧数组可以直接并上去。 代码 # public class MergeSort : BaseSort { /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { Sort(a, 1); } /// <summary> /// 利用分块法进行归并排序。 /// </summary> /// <typeparam name="T">待排序的数组内容。</typeparam> /// <param name="a">待排序的数组。</param> /// <param name="m">分块大小。</param> public void Sort<T>(T[] a, int m) where T : IComparable<T> { var blockNum = (a. ...