2.2.23 # 解答 # 阈值合适时，大约会有10%的性能提升。 阈值在 10 以下都是比较合适的。 代码 # var mergeSort = new MergeSort(); var mergeSortX = new MergeSortX(); var mergeSortUnstable = new MergeSortUnstable(); var n = 1000000; var cutoff = 2; var trialTime = 4; Console.WriteLine("归并排序改进前与改进后的比较："); Console.WriteLine("数组\t耗时1\t耗时2\t阈值\t比率"); for (var i = 0; i < 20; i++) { double mergeSortTime = 0; double mergeSortXTime = 0; mergeSortX.SetCutOff(cutoff); for (var j = 0; j < trialTime; j++) { var a = SortCompare. ...
2.2.24 # 解答 # 约为 $lgN$ 次 代码 # var mergeSortX = new MergeSortX(); var n = 10000; var trialTimes = 10; Console.WriteLine("数组\t平均命中次数"); for (var i = 0; i < 4; i++) { var avgHit = 0; for (var j = 0; j < trialTimes; j++) { mergeSortX.ResetHitTime(); var a = SortCompare.GetRandomArrayInt(n); mergeSortX.Sort(a); avgHit += mergeSortX.GetHitTime(); } Console.WriteLine(n + "\t" + avgHit / trialTimes); n *= 10; } 另请参阅 # Merge 库
2.2.25 # 解答 # 事实上 k 的取值无关紧要，实验也证明了这一点。 算法大致可以分为以下几个步骤 首先将数组划为 k 份， 用一个数组 mids 记录这 k 个子数组的分割位置 随后递归的调用 Sort 方法，将这 k 个子数组排序 随后将这 k 个子数组归并， 每次归并时遍历取 k 个子数组中值最小的一个， 然后对应子数组的指示器 + 1 上面这一步是 $O(k)$ 的， 可以用堆或者败者树优化为对数级别 代码 # /// <summary> /// k 路归并排序。 /// </summary> public class MergeSortKWay : BaseSort { /// <summary> /// 同时归并的数组数目。 /// </summary> /// <value>同时归并的数组数目。</value> public int K { get; set; } /// <summary> /// 默认构造函数。 /// </summary> public MergeSortKWay() { K = 2; } /// <summary> /// 用 k 向归并排序对数组 a 进行排序。 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="a"></param> /// <exception cref="ArgumentOutOfRangeException">数组长度小于 K 值时抛出异常。</exception> public override void Sort<T>(T[] a) { if (K > a. ...
2.2.26 # 解答 # 差距还是比较明显的，由于 Merge 会调用多次，而用于启动递归的 Sort 方法只会调用一次。 代码 # var auxInSort = new AuxInSortMergeSort(); var auxInMerge = new AuxInMergeMergeSort(); var data1 = SortCompare.GetRandomArrayInt(100000); var data2 = new int[data1.Length]; data1.CopyTo(data2, 0); Console.WriteLine("在Sort中创建aux[]\t" + SortCompare.Time(auxInSort, data1) + "ms"); Console.WriteLine("在Merge中创建aux[]\t" + SortCompare.Time(auxInMerge, data2) + "ms"); 另请参阅 # Merge 库
2.2.27 # 解答 # 大致上会是一个对数函数，用 Excel 做了简单的拟合。 原始数据： 表中的 n 代表某一个子数组用尽时两个子数组之和，rest 是另一个未用尽的子数组平均剩余长度，times 代表出现次数，表中删去了出现次数小于 100 次的数据。 n rest times 2 0.331378 48576 3 0.333894 213568 6 0.603899 48576 7 0.596223 82496 14 0.773263 48576 15 0.796285 16960 29 0.879808 15808 30 0.883432 16960 60 0.950848 15808 61 0.935764 576 121 0.985163 7616 122 0.96875 576 243 0.93608 3520 244 1.147569 576 487 0.942255 1472 488 1.020833 576 975 1.078125 448 976 1. ...
2.2.28 # 解答 # 自底向上会快一些，省去了递归过程中函数重复调用的时间。 代码 # var n = 1000; var topBottomMergeSort = new MergeSort(); var bottomUpMergeSort = new MergeSortBu(); var trialTimes = 100; for (var i = 0; i < 4; i++) { Console.Write("数组大小：" + n + "\t"); int time1 = 0, time2 = 0; for (var j = 0; j < trialTimes; j++) { var data1 = SortCompare.GetRandomArrayDouble(n); var data2 = new double[n]; data1.CopyTo(data2, 0); time1 += (int)SortCompare. ...
2.2.29 # 解答 # 完全有序时只需要一次归并（直接输出）， 逆序时需要 n - 1 次归并（退化为插入排序）， 平均需要 n/2 次归并。 所以分别需要 500，500000，500000000 次归并。
2.3.1 # 解答 #
2.3.2 # 解答 #
2.3.3 # 解答 # N / 2 在快速排序中，一个元素要被交换，有以下两种情况 该元素是枢轴，在切分的最后一步被交换 该元素位于枢轴错误的一侧，需要被交换到另一侧去 注意，以上两种情况在一次切分中只会出现一次 首先来看第一种情况，如果一个元素变成了枢轴 那么在之后的切分中该元素会被排除，不存在后续的交换。 因此我们的目标应该是： 最大的元素总是出现在错误的一侧，同时切分的次数尽可能多。 接下来我们来思考如何构造这样的数组 由于我们针对的是最大的元素，因此「错误的一侧」就是枢轴的左侧。 为了使切分的次数尽可能多，我们需要保持最大值移动的距离尽量短。 但如果每次只移动一位的话，下一次切分时最大值就会变成枢轴 例如 4 10 3 5 6，枢轴为 4，交换后数组变为： 4 3 10 5 6 随后 4 和 3 交换 3 4 10 5 6 下一次切分时 10 会变成枢轴，不再参与后续的切分。 因此我们需要让最大值每次移动两个元素。 考虑下面的数组： 2 10 4 1 6 3 8 5 7 9 第一次切分的时候，枢轴为 2，10 和 1 进行交换 数组变为： 2 1 4 10 6 3 8 5 7 9 ...