Sort

2.1.11

2018-6-30
Sort

2.1.11 # 解答 # 希尔排序的官方实现:https://algs4.cs.princeton.edu/21elementary/Shell.java.html 只要稍作修改即可,详情见代码。 代码 # public override void Sort<T>(T[] a) { var n = a.Length; var h = new int[2]; // 预先准备好的 h 值数组 var hTemp = 1; int sequenceSize; for (sequenceSize = 0; hTemp < n; sequenceSize++) { if (sequenceSize >= h.Length) // 如果数组不够大则双倍扩容 { var expand = new int[h.Length * 2]; for (var j = 0; j < h.Length; j++) { expand[j] = h[j]; } h = expand; } h[sequenceSize] = hTemp; hTemp = hTemp * 3 + 1; } for (var t = sequenceSize - 1; 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. ...

2.1.12

2018-6-30
Sort

2.1.12 # 解答 # 结果截图如下,同一个 h 值对应的比值在数组大小不同时保持为一个小常数: 代码 # // 查看最后结果 // 可以发现相同的 h 在数组大小不同时所产生的比值十分接近。 var random = new Random(); var sort = new ShellSort(); var size = 100; for (var i = 0; i < 5; i++) { var a = new double[size]; for (var j = 0; j < size; j++) { a[j] = random.NextDouble() * 100; } Console.WriteLine("ArraySize:" + size); sort.Sort(a); size *= 10; } 另请参阅 # Sort 库

2.1.13

2018-6-30
Sort

2.1.13 # 解答 # 可以用冒泡排序做,具体方法如下: 翻一二两张,是逆序对就交换,否则什么也不做 翻二三两张,是逆序对就交换,否则什么也不做 一直到最后,可以保证最右侧的是最大花色的牌 然后不断重复上述过程,就可以完全排序

2.1.14

2018-6-30
Sort

2.1.14 # 解答 # 用一种类似于冒泡的方法做,具体步骤为: 重复以下步骤,直到全部完成一遍之后没有发生交换 重复以下步骤 n-1 次 如果顶端两张牌逆序,那么交换它们。 将第一张牌放到牌堆底部。 具体步骤图: 我们将牌排成一个环,用一支笔隔开,这里我们标记笔的左侧是牌堆顶部,右侧是牌堆底部。 那么我们能做的三个操作在这里即为: 查看最上面两张牌 = 从笔的位置开始,逆时针查看两张牌。 交换最上面两张牌 = 从笔的位置开始,逆时针选择两张牌并交换。 将最上面的一张牌放到最下面 = 将笔的位置逆时针移动一位。 下面我们开始执行开始说过的操作,目标顺序是自顶向下从小到大排列。 初始情况如图所示: 梅花7 和 红桃4 不是逆序对,直接将笔逆时针移动一位。 红桃4 和 黑桃6 不是逆序对,我们将笔逆时针移动一位。 再看 黑桃6 和 方片A,是逆序对,我们交换并将笔逆时针移动一位。 再看 黑桃6 和 红桃J,是逆序对,我们交换并将笔逆时针移动一位。 现在我们已经操作了 4 次,内部循环结束,我们将笔放回初始位置。 这样一次循环之后,我们就把最大的牌放在了最下面,依次类推即可完全排序。 另请参阅 # Sorting a deque using limited operations?-Stock Overflow

2.1.15

2018-6-30
Sort

2.1.15 # 解答 # 选择排序 交换(也就是 Exch() 方法)需要一个额外空间,这里的条件满足。 现在我们应该使交换次数最少,选择排序只需要 N 次交换,比插入排序平均 N^2/4 少(N > 2)。

2.1.16

2018-6-30
Sort

2.1.16 # 解答 # 如果移动数据时新建了对象,那么虽然值没有改变,但是数组中的对象被修改了。 代码 # 插入排序中的 Exch() 换成了如下方式: string temp = new string(s[i].ToCharArray()); s[i] = s[min]; s[min] = temp; 全部程序代码如下: var test = new[] { "a", "b", "d", "c", "e" }; Console.WriteLine(CheckArraySort(test)); Console.WriteLine(CheckSelectionSort(test)); // 测试 Array.Sort() 方法。 static bool CheckArraySort(string[] a) { var backup = new string[a.Length]; a.CopyTo(backup, 0); Array.Sort(a); foreach (var n in a) { var isFind = false; for (var i = 0; i < a. ...

2.1.17

2018-6-30
Sort

2.1.17 # 解答 # 选择排序: 插入排序: 代码 # 使用一个 timer 按一定时间重绘数组,排序算法里面一次循环后等待一段时间再进行下一次循环。(这并不是一个很好的方法,但对于演示来说足够了) 这里排序算法是另开线程运行的,防止 Sleep 的时候让程序无响应。 选择排序: using System; using System.Drawing; using System.Windows.Forms; using System.Threading; namespace _2._1._17 { public partial class Form2 : Form { double[] randomDoubles; public Form2(int N) { InitializeComponent(); this.randomDoubles = new double[N]; Random random = new Random(); for (int i = 0; i < N; i++) { this.randomDoubles[i] = random.NextDouble() * 0.8 + 0.2; } drawPanel(); this.timer1.Interval = 60; this. ...

2.1.18

2018-6-30
Sort

2.1.18 # 解答 # 选择排序 插入排序 代码 # 与上题类似,但要特别标出移动的元素。 选择排序: using System; using System.Drawing; using System.Windows.Forms; using System.Threading; namespace _2._1._18 { public partial class Form2 : Form { double[] randomDoubles; int sortI; int sortJ; int sortMin; public Form2(int N) { InitializeComponent(); this.randomDoubles = new double[N]; Random random = new Random(); for (int i = 0; i < N; i++) { this.randomDoubles[i] = random.NextDouble() * 0.8 + 0.2; } } /// <summary> /// 选择排序。 /// </summary> private void SelectionSort() { for (this. ...

2.1.19

2018-6-30
Sort

2.1.19 # 解答 # 不得不说这道题意外的难。 放上论文链接:Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences) 这篇论文的第二章给出了一种构造最坏序列的方法,当然理想最坏(n^(3/2))是达不到的了。 最后结果是 793 次。 @杨晗 通过随机输入获得了一个理论最坏的输入序列,见:https://github.com/YangXiaoHei/Algorithms/blob/master/Ch_2_1_Elementary_Sorts/Practise_2_1_19.java 这个序列是: 48, 46, 54, 97, 83, 69, 76, 25, 10, 5, 87, 12, 21, 99, 61, 33, 30, 47, 57, 4, 36, 42, 98, 66, 100, 17, 94, 81, 11, 77, 24, 89, 73, 53, 38, 7, 29, 8, 27, 23, 56, 70, 60, 85, 39, 65, 9, 75, 15, 67, 64, 22, 51, 82, 43, 3, 37, 91, 45, 13, 34, 63, 74, 71, 95, 55, 80, 92, 2, 19, 62, 40, 84, 41, 50, 88, 86, 59, 28, 44, 72, 68, 14, 35, 93, 26, 18, 78, 31, 58, 96, 6, 1, 90, 49, 16, 52, 79, 32, 20 会比较 999 次。 ...

2.1.20

2018-6-30
Sort

2.1.20 # 解答 # 由于每次 h 排序都是插入排序,希尔排序最好情况就是插入排序的最好情况,也就是已排序的数组。