2019-1-15
2.5.21 # 解答 # 与之前的版本号比较十分类似，对数组进行包装，然后按照次序依次比较即可。
internal class Vector : IComparable<Vector> { private readonly int[] _data; public int Length { get; set; } public Vector(int[] data) { _data = data; Length = data.Length; } public int CompareTo(Vector other) { var maxN = Math.Max(Length, other.Length); for (var i = 0; i < maxN; i++) { var comp = _data[i].CompareTo(other._data[i]); if (comp != 0) return comp; } return Length.CompareTo(other.Length); } public override string ToString() { var sb = new StringBuilder(); for (var i = 0; i < Length; i++) { if (i !
...
2019-1-15
2.5.22 # 解答 # 建立最小堆和最大堆，最小堆保存卖家的报价，最大堆保存买家的报价。
如果最小堆中的最低卖出价低于最大堆的最高买入价，交易达成，交易份额较大的一方需要重新回到堆内。
测试结果：
代码 # // 输入格式： buy 20.05 100 var buyer = new MaxPq<Ticket>(); var seller = new MinPq<Ticket>(); var n = int.Parse(Console.ReadLine()); for (var i = 0; i < n; i++) { var ticket = new Ticket(); var item = Console.ReadLine().Split(' '); ticket.Price = double.Parse(item[1]); ticket.Share = int.Parse(item[2]); if (item[0] == "buy") buyer.Insert(ticket); else seller.Insert(ticket); } while (!buyer.IsEmpty() && !seller.IsEmpty()) { if (buyer.Max().Price < seller.
...
2019-1-21
2.5.23 # 解答 # 这里我们使用 Floyd-Rivest 算法进行优化，大致思想是：
我们期望第 $k$ 大的元素位于 a[k] 附近，因此优先对 a[k] 附近的区域进行选择。
每次切分时枢轴都选择 a[k]，先递归对样本区域选择，再对整个数组进行选择。
运行示意图：
测试结果：
代码 # // Floyd–Rivest 方法优化，令 a[k] 变成第 k 小的元素。 static T SelectInternal<T>(T[] a, int lo, int hi, int k) where T : IComparable<T> { if (k < 0 || k > a.Length) { throw new IndexOutOfRangeException("SelectInternal elements out of bounds"); } while (hi > lo) { if (hi - lo > 600) { var n = hi - lo + 1; var i = k - lo + 1; var z = (int)Math.
...
2019-1-23
2.5.24 # 解答 # 官方解答：https://algs4.cs.princeton.edu/25applications/StableMinPQ.java.html
在元素插入的同时记录插入顺序，比较的时候把插入顺序也纳入比较。
对于值一样的元素，插入顺序在前的的元素比较小。
交换的时候需要同时交换插入次序。
代码 # public class MinPqStable<TKey> : IMinPq<TKey>, IEnumerable<TKey> where TKey : IComparable<TKey> { /// <summary> /// 保存元素的数组。 /// </summary> /// <value>保存元素的数组。</value> protected TKey[] Pq; /// <summary> /// 堆中元素的数量。 /// </summary> /// <value>堆中元素的数量。</value> protected int N; /// <summary> /// 元素的插入次序。 /// </summary> /// <value>元素的插入次序。</value> private long[] _time; /// <summary> /// 元素的插入次序计数器。 /// </summary> /// <value>元素的插入次序计数器。</value> private long _timeStamp = 1; // 元素插入次序计数器。 /// <summary> /// 默认构造函数。 /// </summary> public MinPqStable() : this(1) { } /// <summary> /// 建立指定容量的最小堆。 /// </summary> /// <param name="capacity">最小堆的容量。</param> public MinPqStable(int capacity) { _time = new long[capacity + 1]; Pq = new TKey[capacity + 1]; N = 0; } /// <summary> /// 删除并返回最小元素。 /// </summary> /// <returns>最小元素。</returns> /// <exception cref="ArgumentOutOfRangeException">如果堆为空则抛出该异常。</exception> /// <remarks>如果希望获得最小值但不删除它，请使用 <see cref="Min"/>。</remarks> public TKey DelMin() { if (IsEmpty()) throw new InvalidOperationException("Priority Queue Underflow"); var min = Pq[1]; Exch(1, N--); Sink(1); Pq[N + 1] = default; _time[N + 1] = 0; if ((N > 0) && (N == Pq.
...
2019-1-24
2.5.25 # 解答 # 官方解答见：https://algs4.cs.princeton.edu/25applications/Point2D.java.html
这些比较器都以嵌套类的形式在 Point2D 中定义。
静态比较器直接在类中以静态成员的方式声明。
非静态比较器则需要提供工厂方法，该方法新建并返回对应的比较器对象。
代码 # /// <summary> /// 按照 X 顺序比较。 /// </summary> private class XOrderComparer : Comparer<Point2D> { public override int Compare(Point2D x, Point2D y) { if (x.X < y.X) { return -1; } if (x.X > y.X) { return 1; } return 0; } } /// <summary> /// 按照 Y 顺序比较。 /// </summary> private class YOrderComparer : Comparer<Point2D> { public override int Compare(Point2D x, Point2D y) { if (x.
...
2019-1-24
2.5.26 # 解答 # 提示中已经给出了方法，使用上一题编写的比较器进行排序即可。
效果演示：
代码 # 绘图部分代码：
using System.Collections.Generic; using System.Drawing; using System.Windows.Forms; using SortApplication; namespace _2._5._26 { public partial class Form2 : Form { Graphics panel; List<Point2D> points; Point2D startPoint; double maxX = 0, maxY = 0; public Form2() { InitializeComponent(); } /// <summary> /// 显示并初始化绘图窗口。 /// </summary> public void Init() { Show(); this.panel = CreateGraphics(); this.points = new List<Point2D>(); this.startPoint = null; } /// <summary> /// 向画板中添加一个点。 /// </summary> /// <param name="point"></param> public void Add(Point2D point) { this.
...
2019-1-24
2.5.27 # 解答 # 类似于索引排序的做法，访问数组都通过一层索引来间接实现。
首先创建一个数组 index，令 index[i] = i。
排序时的交换变成 index 数组中元素的交换，
读取元素时使用 a[index[i]] 而非 a[i] 。
代码 # // 间接排序。 static int[] IndirectSort<T>(T[] keys) where T : IComparable<T> { var n = keys.Length; var index = new int[n]; for (var i = 0; i < n; i++) index[i] = i; for (var i = 0; i < n; i++) for (var j = i; j > 0 && keys[index[j]].
...
2019-1-24
2.5.28 # 解答 # 官方解答：https://algs4.cs.princeton.edu/25applications/FileSorter.java.html
先获得目录里的所有文件名，然后排序输出即可。
代码 # var directoryName = Console.ReadLine(); if (!Directory.Exists(directoryName)) { Console.WriteLine(directoryName + " doesn't exist or isn't a directory"); return; } var directoryFiles = Directory.GetFiles(directoryName); Array.Sort(directoryFiles); for (var i = 0; i < directoryFiles.Length; i++) Console.WriteLine(directoryFiles[i]);
2019-1-24
2.5.29 # 解答 # 首先定义一系列比较器，分别根据文件大小、文件名和最后修改日期比较。
然后修改 Less 的实现，接受一个比较器数组，使用数组中的比较器依次比较，直到比较结果为两者不相同。
最后使用插入排序作为稳定排序，传入比较器数组用于 Less 函数。
代码 # var arguments = Console.ReadLine().Split(' '); var directoryPath = arguments[0]; var filenames = Directory.GetFiles(directoryPath); var fileInfos = new FileInfo[filenames.Length]; for (var i = 0; i < filenames.Length; i++) fileInfos[i] = new FileInfo(filenames[i]); var comparers = new List<Comparer<FileInfo>>(); for (var i = 1; i < arguments.Length; i++) { var command = arguments[i]; switch (command) { case "-t": comparers.Add(new FileTimeStampComparer()); break; case "-s": comparers.
...
2019-1-24
2.5.30 # 解答 # 不妨按照升序排序，$x_{ij}$ 代表第 $i$ 行第 $j$ 列的元素。
首先保证每列都是有序的。
对第一行排序，对于第一行的元素 $x_{1i}$ ，排序结果无非两种。
要么 $x_{1i}$ 不改变，要么和更小的元素进行交换。
显然，无论哪种情况，第 $i$ 列都是有序的。
因此对第一行排序之后，第一行有序，每一列都分别有序。
之后我们对第二行排序，考虑元素 $x_{11}$。
此时 $x_{11}$ 小于第一列的所有其他元素，也小于第一行的所有其他元素。
又每一列都分别有序，因此 $x_{11}$ 是整个矩阵的最小值，第二行不存在比它小的元素。
考虑使用选择排序，我们把第二行的最小值和 $x_{21}$ 交换，第一列仍然有序。
现在去掉第一列，对剩下的矩阵做一样的操作，可以将第二行依次排序。
同时保证第二行的元素都小于同列的第一行元素。
接下来的行都可以依次类推，最终将整个矩阵的所有行排序，定理得证。