2019-1-8
2.5.11 # 解答 # 结果如下，其中快速排序去掉了一开始打乱数组的步骤：
只有快速排序和堆排序会进行交换，剩下四种排序都不会进行交换。
插入排序在排序元素完全相同的数组时只会进行一次遍历，不会交换。
选择排序第 i 次找到的最小值就是 a[i] ，只会让 a[i] 和 a[i] 交换，不会影响顺序。
希尔排序和插入排序类似，每轮排序都不会进行交换。
归并排序是稳定的，就本例而言，只会从左到右依次归并，不会发生顺序变化。
快速排序在遇到相同元素时会交换，因此顺序会发生变化，且每次都是对半切分。
堆排序在删除最大元素时会将第一个元素和最后一个元素交换，使元素顺序发生变化。
代码 # // 插入排序 Console.WriteLine("Insertion Sort"); Test(new InsertionSort(), 7, 1); // 选择排序 Console.WriteLine("Selection Sort"); Test(new SelectionSort(), 7, 1); // 希尔排序 Console.WriteLine("Shell Sort"); Test(new ShellSort(), 7, 1); // 归并排序 Console.WriteLine("Merge Sort"); Test(new MergeSort(), 7, 1); // 快速排序 Console.WriteLine("Quick Sort"); var quick = new QuickSortAnalyze { NeedShuffle = false, NeedPath = false }; Test(quick, 7, 1); // 堆排序 Console.
...
2019-1-9
2.5.12 # 解答 # 官方解答：https://algs4.cs.princeton.edu/25applications/SPT.java.html
把任务按照处理时间升序排序即可。
建立 Job 类，保存任务的名称和处理时间，并实现了 IConparable<Job> 接口。
internal class Job : IComparable<Job> { public readonly string Name; public readonly double Time; public Job(string name, double time) { Name = name; Time = time; } public int CompareTo(Job other) { return Time.CompareTo(other.Time); } } 代码 # var n = int.Parse(Console.ReadLine()); var jobs = new Job[n]; for (var i = 0; i < n; i++) { var input = Console.
...
2019-1-10
2.5.13 # 解答 # 官方解答见：https://algs4.cs.princeton.edu/25applications/LPT.java.html
使用上题的 Job 类，在本题建立 Processor 类来代表处理器，定义如下：
internal class Processor : IComparable<Processor> { private readonly List<Job> _jobs = new(); private double _busyTime; public void Add(Job job) { _jobs.Add(job); _busyTime += job.Time; } public int CompareTo(Processor other) { return _busyTime.CompareTo(other._busyTime); } public override string ToString() { var sb = new StringBuilder(); var nowList = _jobs.ToArray(); for (var i = 0; i < nowList.Length; i++) { sb.AppendLine(nowList[i].Name + " " + nowList[i].
...
2019-1-11
2.5.14 # 解答 # 官方解答：https://algs4.cs.princeton.edu/25applications/Domain.java.html
按照逆域名排序，例如输入的是 com.google 和 com.apple ，
比较的时候是按照 google.com 和 apple.com 进行比较的。
排序结果自然是 apple.com, google.com。
编写的 Domain 类，CompareTo() 中是按照倒序进行比较的。
internal class Domain : IComparable<Domain> { private readonly string[] _fields; private readonly int _n; /// <summary> /// 构造一个域名。 /// </summary> /// <param name="url">域名的 url。</param> public Domain(string url) { _fields = url.Split('.'); _n = _fields.Length; } public int CompareTo(Domain other) { var minLength = Math.Min(_n, other._n); for (var i = 0; i < minLength; i++) { var c = _fields[minLength - i - 1].
...
2019-1-11
2.5.15 # 解答 # 利用上一题的逆域名排序将域名相同的电子邮件分在一起。
代码 # // 利用上一题的逆域名排序，将相同的域名放在一起。 var emails = new Domain[5]; emails[0] = new Domain("wayne@cs.princeton.edu"); emails[1] = new Domain("windy@apple.com"); emails[2] = new Domain("rs@cs.princeton.edu"); emails[3] = new Domain("ike@ee.princeton.edu"); emails[4] = new Domain("admin@princeton.edu"); Array.Sort(emails); for (var i = 0; i < emails.Length; i++) { Console.WriteLine(emails[i]); }
2019-1-12
2.5.16 # 解答 # 官方解答：https://algs4.cs.princeton.edu/25applications/California.java.html
数据来源：https://introcs.cs.princeton.edu/java/data/california-gov.txt
建立一个 string 的比较器，按照题目给定的顺序比较。
private class CandidateComparer : IComparer<string> { private static readonly string order = "RWQOJMVAHBSGZXNTCIEKUPDYFL"; public int Compare(string x, string y) { int n = Math.Min(x.Length, y.Length); for (int i = 0; i < n; i++) { int a = order.IndexOf(x[i]); int b = order.IndexOf(y[i]); if (a != b) return a.CompareTo(b); } return x.Length.CompareTo(y.Length); } } 代码 # // 数据来源：https://introcs.cs.princeton.edu/java/data/california-gov.txt var sr = new StreamReader(File.
...
2019-1-12
2.5.17 # 解答 # 用一个 Wrapper 类包装准备排序的元素，在排序前同时记录元素的内容和下标。
随后对 Wrapper 数组排序，相同的元素会被放在一起，检查它们的下标是否是递增的。
如果不是递增的，则排序算法就是不稳定的；否则排序算法就有可能是稳定的。 （不稳定的排序算法也可能不改变相同元素的相对位置，比如用选择排序对有序数组排序）
代码 # var data = new[] { 7, 7, 4, 8, 8, 5, 1, 7, 7 }; var merge = new MergeSort(); var insertion = new InsertionSort(); var shell = new ShellSort(); var selection = new SelectionSort(); var quick = new QuickSort(); Console.WriteLine("Merge Sort: " + CheckStability(data, merge)); Console.WriteLine("Insertion Sort: " + CheckStability(data, insertion)); Console.WriteLine("Shell Sort: " + CheckStability(data, shell)); Console.
...
2019-1-14
2.5.18 # 解答 # 用和上题一样的 Wrapper 类进行排序。
排序之后，相同的元素会被放在一起，形成一个个子数组。
根据事先保存的原始下标对它们进行排序，即可将不稳定的排序稳定化。
结果：
代码 # var data = new[] { 5, 7, 3, 4, 7, 3, 6, 3, 3 }; var quick = new QuickSort(); var shell = new ShellSort(); Console.WriteLine("Quick Sort"); Stabilize(data, quick); Console.WriteLine(); Console.WriteLine("Shell Sort"); Stabilize(data, shell); static void Stabilize<T>(T[] data, BaseSort sort) where T : IComparable<T> { var items = new Wrapper<T>[data.Length]; for (var i = 0; i < data.
...
2019-1-14
2.5.19 # 解答 # 官方解答： Kendall Tau：https://algs4.cs.princeton.edu/25applications/KendallTau.java.html
Inversion：https://algs4.cs.princeton.edu/22mergesort/Inversions.java.html
由书中 2.5.3.2 节得，两个数组之间的 Kendall Tau 距离即为两数组之间顺序不同的数对数目。
如果能够把其中一个数组变成标准排列（即 1,2,3,4... 这样的数组），
那么此时 Kendall Tau 距离就等于另一个数组中的逆序对数量。
现在我们来解决如何把一个数组 a 变成标准排列的方法。
也就是找到函数 $ f(x) $，使得 $ f(a[i])=i $ ，这样的函数其实就是数组 a 的逆数组。
如下图所示，逆数组 ainv 即为满足 ainv[a[i]] = i 的数组。
获得逆数组之后，对另一个数组 b 做同样的变换，令数组 bnew[i] = ainv[b[i]] 。
即 ainv[a[i]] = i, ainv[b[i]] = bnew[i] 。
于是问题转化为了 bnew 和标准排列之间的 Kendall Tau 距离，即 bnew 的逆序对数量。
逆序对数量的求法见 2-2-19。
代码 # int[] testA = { 0, 3, 1, 6, 2, 5, 4 }; int[] testB = { 1, 0, 3, 6, 4, 2, 5 }; Console.
...
2019-1-14
2.5.20 # 解答 # 我们以事件为单位进行处理，每个事件包含任务名，记录时刻和开始/结束标记。
随后按照时间从小到大排序，遍历事件数组。
设开始的时候机器空闲，设置计数器，作为当前正在运行的任务数量。
当遇到开始事件时，计数器加一；遇到结束事件时，计数器减一。
如果计数器加一之前计数器为 0，说明空闲状态结束，记录并更新空闲时间，当前时间为忙碌开始的时间。
如果计数器减一之后计数器为 0，说明忙碌状态结束，记录并更新忙碌时间，当前时间为空闲开始的时间。
测试结果：
代码 # var nowRunning = 0; // 正在运行的程序数量 var maxIdle = 0; var maxBusy = 0; var items = int.Parse(Console.ReadLine()); var jobs = new JobEvent[items * 2]; for (var i = 0; i < jobs.Length; i += 2) { jobs[i] = new JobEvent(); jobs[i + 1] = new JobEvent(); jobs[i].IsFinished = false; // 开始事件 jobs[i + 1].
...