2018-6-30
2.1.21 # 解答 # 事实上官方给出来的 Date 类以及 Transaction 类都已经实现了这些接口。
Date 类：Date.java
Transaction 类：Transaction.java
代码 # var a = new Transaction[4]; a[0] = new Transaction("Turing 6/17/1990 644.08"); a[1] = new Transaction("Tarjan 3/26/2002 4121.85"); a[2] = new Transaction("Knuth 6/14/1999 288.34"); a[3] = new Transaction("Dijkstra 8/22/2007 2678.40"); Console.WriteLine("Unsorted"); for (var i = 0; i < a.Length; i++) { Console.WriteLine(a[i]); } Console.WriteLine(); Console.WriteLine("Sort by amount"); var insertionSort = new InsertionSort(); insertionSort.Sort(a, new Transaction.HowMuchOrder()); for (var i = 0; i < a.
...
2018-6-30
2.1.22 # 解答 # 和上题类似，只要传入事先写好的比较器就可以了。
代码 # var a = new Transaction[4]; // 样例输入 // Turing 6/17/1990 644.08 // Tarjan 3/26/2002 4121.85 // Knuth 6/14/1999 288.34 // Dijkstra 8/22/2007 2678.40 for (var i = 0; i < a.Length; i++) { var input = Console.ReadLine(); a[i] = new Transaction(input); } var insertionSort = new InsertionSort(); Console.WriteLine("Unsorted"); for (var i = 0; i < a.Length; i++) { Console.WriteLine(a[i]); } Console.WriteLine(); Console.WriteLine("Sort by date"); insertionSort.
...
2018-6-30
2.1.23 # 解答 # 方法多种多样。
首先是冒泡，见习题 2.1.13
插入排序也可以，如下：
从前往后不断翻牌，
对于翻到的每张牌，一直和之前的牌交换，
直至前面的牌比它小或者它已经是第一张了。
也可以用基数排序
从前向后依次翻开牌，
按照花色分成四堆，
然后按花色从大到小重新排列。
比较符合直觉的是选择排序
寻找最小的牌并放到第一位，
寻找范围向右缩减一位，重复上一步，直到最后一张。
还有其他方法，这里不再赘述。
2018-6-30
2.1.24 # 解答 # 如果使用官方的实现（InsertionX.java），最后结果可能会比一般插入排序慢，因为它是用冒泡的方法找最小值的。
一般做法是在待排序数组的最前端插入一个很小的值（比如 int.MinValue），然后对 a[1]~a[n] 排序。
代码 # 参考官方实现的插入排序：
public class InsertionSort : BaseSort { /// <summary> /// 利用插入排序将数组按升序排序。 /// </summary> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { var n = a.Length; var exchanges = 0; for (var i = n - 1; i > 0; i--) { if (Less(a[i], a[i - 1])) { Exch(a, i, i - 1); exchanges++; } } if (exchanges == 0) return; for (var i = 1; i < n; i++) { for (var j = i; Less(a[j], a[j - 1]); --j) { Exch(a, j, j - 1); } Debug.
...
2018-6-30
2.1.25 # 解答 # 使用依次赋值的方式腾出空间，到达指定位置之后再把元素插入。
看代码会方便理解一点。
官方实现：InsertionX.java。
代码 # public class InsertionSort : BaseSort { /// <summary> /// 利用插入排序将数组按升序排序。 /// </summary> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { var n = a.Length; var exchanges = 0; for (var i = n - 1; i > 0 ; i--) { if (Less(a[i], a[i - 1])) { Exch(a, i, i - 1); exchanges++; } } if (exchanges == 0) return; for (var i = 2; i < n; i++) { var j = i; var v = a[i]; while (Less(v, a[j - 1])) { a[j] = a[j - 1]; j--; } a[j] = v; Debug.
...
2018-6-30
2.1.26 # 解答 # 直接针对特殊值的话显然会快很多。
代码 # 直接把泛型改成 int 即可。
public class InsertionSort { /// <summary> /// 利用插入排序将数组按升序排序。 /// </summary> /// <param name="a">需要排序的数组。</param> public void Sort(int[] a) { var n = a.Length; for (var i = 0; i < n; i++) { for (var j = i; j > 0 && a[j] < a[j - 1]; --j) { var t = a[j]; a[j] = a[j - 1]; a[j - 1] = t; } } } } 另请参阅 # Sort 库
2018-6-30
2.1.27 # 解答 # 数据比较大的时候会比较明显。
代码 # var n = 128; var random = new Random(); double shellPrev = 1; double insertionPrev = 1; double selectionPrev = 1; while (n < 65538) { var testShell = new int[n]; var testInsertion = new int[n]; var testSelection = new int[n]; for (var i = 0; i < n; i++) { testShell[i] = random.Next(); testInsertion[i] = testShell[i]; testSelection[i] = testShell[i]; } Console.WriteLine("数组大小：" + n); Console.
...
2018-6-30
2.1.28 # 解答 # 插入排序会比选择排序快上许多，当然增长级别不变。
代码 # var n = 1024; var random = new Random(); double insertionPrev = 1; double selectionPrev = 1; while (n < 65538) { var testInsertion = new int[n]; var testSelection = new int[n]; for (var i = 0; i < n; i++) { testInsertion[i] = random.Next(2); testSelection[i] = testInsertion[i]; } Console.WriteLine("数组大小：" + n); Console.Write("Insertion Sort:"); var insertionNow = SortCompare.Time(new InsertionSort(), testInsertion); Console.WriteLine(insertionNow + "\tNow/Prev=" + insertionNow / insertionPrev); Console.
...
2018-6-30
2.1.29 # 解答 # 当然是题目给出的递增序列更快啦，因为这个序列就是作者提出来的嘛。
（论文链接： http://linkinghub.elsevier.com/retrieve/pii/0196677486900015）
代码 # 修改了一下 shellsort，让它按照给定的 h 序列排序。
public class ShellSort : BaseSort { /// <summary> /// 利用希尔排序将数组按升序排序。 /// </summary> /// <typeparam name="T">待排序的元素类型。</typeparam> /// <param name="a">待排序的数组。</param> /// <param name="h">需要使用的递增序列。</param> public void Sort<T>(T[] a, int[] h) where T : IComparable<T> { var n = a.Length; var t = 0; while (h[t] < a.Length) { t++; if (t >= h.Length) break; } t--; for ( ; t >= 0; t--) { for (var i = h[t]; i < n; i++) { for (var j = i; j >= h[t] && Less(a[j], a[j - h[t]]); j -= h[t]) { Exch(a, j, j - h[t]); } } Debug.
...
2018-6-30
2.1.30 # 解答 # 2，3，4
t 越大的话，按照这个递增序列，10^6 次能够满足的 h 也就越少。
代码 # // t = 2, 3, 4 // t 大于 10 之后，由于每次排序 h 缩减的太快， // 时间会越来越近似于直接插入排序。 var array = SortCompare.GetRandomArrayInt(1000000); var array2 = new int[array.Length]; array.CopyTo(array2, 0); var timer = new Stopwatch(); var bestTimes = new long[3]; var bestTs = new long[3]; for (var i = 0; i < bestTimes.Length; i++) { bestTimes[i] = long.MaxValue; bestTs[i] = int.MaxValue; } var shellSort = new ShellSort(); for (var t = 2; t <= 1000000; t++) { Console.
...