2018-6-30
2.1.31 # 解答 # 这里截取数据量比较大的时候的数据。
插入排序和选择排序显然都是平方级别的。
希尔排序猜测是线性的，实际上要比线性大一点（次平方级）。
代码 # var n = 1000; var insertion = new InsertionSort(); var selection = new SelectionSort(); var shell = new ShellSort(); double prevInsertion = 0; double prevSelection = 0; double prevShell = 0; for (var i = 0; i < 10; i++) { Console.WriteLine("N:" + n); var array = SortCompare.GetRandomArrayInt(n); var arrayBak = new int[n]; array.CopyTo(arrayBak, 0); Console.WriteLine("\tInsertion Sort"); var now = SortCompare.
...
2018-6-30
2.1.32 # 解答 # 基本上都是这么个样子：
代码 # using System; using System.Drawing; using System.Linq; using System.Windows.Forms; using Sort; namespace _2._1._32 { public partial class Form2 : Form { BaseSort sort; int n; double[] result; /// <summary> /// 构造一个绘图结果窗口。 /// </summary> /// <param name="sort">用于做测试的排序算法。</param> /// <param name="n">用于测试的初始数据量。</param> public Form2(BaseSort sort, int n) { InitializeComponent(); this.sort = sort; this.n = n; this.result = Test(n); this.timer1.Interval = 1000; this.timer1.Start(); } /// <summary> /// 执行八次耗时测试，每次数据量翻倍。 /// </summary> /// <param name="n">初始数据量。</param> /// <returns>测试结果数据。</returns> public double[] Test(int n) { double[] result = new double[8]; for (int i = 0; i < result.
...
2018-6-30
2.1.33 # 解答 # 这里每次结果的 Y 轴位置都是随机生成的，这样图像会好看点。
X 轴代表消耗的时间。
选择排序：
插入排序：
希尔排序：
代码 # using System; using System.Collections.Generic; using System.Drawing; using System.Linq; using System.Windows.Forms; using Sort; namespace _2._1._33 { public partial class Form2 : Form { List<double> resultList; List<float> resultYList; Rectangle clientRect; Rectangle drawRect; BaseSort sort; int n; /// <summary> /// 构造一个绘制结果窗口。 /// </summary> /// <param name="sort">用于测试的排序算法。</param> /// <param name="n">测试算法是生成的数据量。</param> public Form2(BaseSort sort, int n) { InitializeComponent(); this.resultList = new List<double>(); this.
...
2018-6-30
2.1.34 # 解答 # 代码 # var insertionSort = new InsertionSort(); var selectionSort = new SelectionSort(); var shellSort = new ShellSort(); // 逆序 Console.WriteLine("逆序"); Console.WriteLine("Insertion Sort Time: " + ReverseSortTest(insertionSort)); Console.WriteLine("Selection Sort Time: " + ReverseSortTest(selectionSort)); Console.WriteLine("Shell Sort Time: " + ReverseSortTest(shellSort)); // 顺序 Console.WriteLine("顺序"); Console.WriteLine("Insertion Sort Time: " + SortedSortTest(insertionSort)); Console.WriteLine("Selection Sort Time: " + SortedSortTest(selectionSort)); Console.WriteLine("Shell Sort Time: " + SortedSortTest(shellSort)); // 主键相同 Console.WriteLine("主键相同"); Console.WriteLine("Insertion Sort Time: " + EqualSortTest(insertionSort)); Console.
...
2018-6-30
2.1.35 # 解答 # 难点是如何生成符合这些分布的随机数。
Java 的话官方给的 stdRandom 里面都有相应的实现。
结果：
代码 # 几种随机数的实现：
public static class SortUtil { /// <summary> /// 随机数发生器，所有对象共享同一个随机数发生器。 /// </summary> public static Random UniformGenerator = new(); /// <summary> /// 产生符合正态分布的随机数。 /// </summary> /// <param name="average">正态分布的期望值 μ。</param> /// <param name="standardDeviation">正态分布的标准差 σ。</param> /// <returns>符合正态分布的随机数。</returns> public static double Normal(double average, double standardDeviation) { var u1 = UniformGenerator.NextDouble(); var u2 = UniformGenerator.NextDouble(); var z0 = Math.Sqrt(-2.0 * Math.Log(u1)) * Math.
...
2018-6-30
2.1.36 # 解答 # 最后结果：
代码 # // 选择排序的耗时与输入值的内容无关，不受影响。 // 对于插入排序，以上几种情况都是重复值较多的情况，插入排序的速度会加快。 // 希尔排序本质上也是插入排序，因此也会更快一些。 var n = 10000; var insertionSort = new InsertionSort(); var selectionSort = new SelectionSort(); var shellSort = new ShellSort(); var arraySelection = new int[n]; var arrayShell = new int[n]; // 对照，完全随机 var arrayInsertion = HalfZeroHalfOne(n); arrayInsertion.CopyTo(arraySelection, 0); arrayInsertion.CopyTo(arrayShell, 0); Console.WriteLine("totally random"); Console.WriteLine("Insertion Sort:" + SortCompare.TimeRandomInput(insertionSort, n, 1)); Console.WriteLine("Selection Sort:" + SortCompare.TimeRandomInput(selectionSort, n, 1)); Console.WriteLine("Shell Sort:" + SortCompare.
...
2018-6-30
2.1.37 # 解答 # 主要说一下第二个的实现，把一个数组按 10 位进行打乱即可。
代码 # // 选择排序的性能只与数组大小有关，以上三种情况耗时都是近似的。 // 插入排序的性能与逆序对数量有关，部分有序的情况下耗时会小于完全随机。 // 希尔排序与插入排序类似。 var insertionSort = new InsertionSort(); var selectionSort = new SelectionSort(); var shellSort = new ShellSort(); var n = 100000; var insertionArray = new int[n]; var shellArray = new int[n]; // 完全随机的对照 Console.WriteLine("totally random"); Console.WriteLine("Selection Sort:" + SortCompare.TimeRandomInput(selectionSort, n, 1)); Console.WriteLine("Insertion Sort:" + SortCompare.TimeRandomInput(insertionSort, n, 1)); Console.WriteLine("Shell Sort:" + SortCompare.TimeRandomInput(shellSort, n, 1)); // 95% 有序，其余部分为随机值。 var selectionArray = Sorted95Random5(n); selectionArray.
...
2018-6-30
2.1.38 # 解答 # 这里实现了一个 Pair 类，用来排序。
每一个元素都有相应的 key 值和 value 值，排序时只使用 key 值进行排序。
代码 # var n = 10000; var results = TestA(n); Console.WriteLine("string + double"); Console.WriteLine("Insertion Sort:" + results[0]); Console.WriteLine("Selection Sort:" + results[1]); Console.WriteLine("Shell Sort:" + results[2]); results = TestB(n); Console.WriteLine("double + 10 string"); Console.WriteLine("Insertion Sort:" + results[0]); Console.WriteLine("Selection Sort:" + results[1]); Console.WriteLine("Shell Sort:" + results[2]); results = TestC(n); Console.WriteLine("int + int[]"); Console.WriteLine("Insertion Sort:" + results[0]); Console.WriteLine("Selection Sort:" + results[1]); Console.
...
2018-7-4
2.2.1 # 解答 #
2018-7-4
2.2.2 # 解答 #