写在前面
整个项目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp
查找更为方便的版本见：https://alg4.ikesnowy.com
这一节内容可能会用到的库文件有 Merge，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。
习题&题解
2.2.1
解答
2.2.2
解答
2.2.3
解答
2.2.4
解答
是的，必须要两个子数组都有序时归并才能得到正确结果。
如果说数组不有序的话，那么最后只能得到两个数组的混合。
合并后的数组中，属于原有数组的元素的相对顺序不会被改变。
例如子数组 1 3 1 和 2 8 5 原地归并。
结果是 1 2 3 1 8 5，其中 1 3 1 和 2 8 5 的相对顺序不变。
2.2.5
解答
每次归并子数组的大小和顺序如下：
自顶向下
2, 3, 2, 5, 2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 3, 2, 5, 10, 20, 2, 3, 2, 5, 2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 2, 4, 9, 19, 39
自底向上
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 8, 8, 8, 8, 7, 16, 16, 32, 39
2.2.6
解答
灰色是上限，蓝点是自顶向下，红点是自底向上。
由于两种排序访问数组的次数是一样的，因此蓝点和红点重合。
代码
给出绘图部分的代码：
using System; using System.Windows.Forms; using System.Drawing; using Merge; namespace _2._2._6 { /* * 2.2.6 * * 编写一个程序来计算自顶向下和自底向上的归并排序访问数组的准确次数。 * 使用这个程序将 N=1 至 512 的结果绘成曲线图， * 并将其和上限 6NlgN 相比较。 * */ static class Program { /// <summary> /// 应用程序的主入口点。 /// </summary> [STAThread] static void Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Compute(); Application.Run(new Form1()); } static void Compute() { MergeSort mergeSort = new MergeSort(); MergeSortBU mergeSortBU = new MergeSortBU(); int[] mergeResult = new int[10]; int[] mergeResultBU = new int[10]; int[] upperBound = new int[10]; // 进行计算 int dataSize = 1; for (int i = 0; i < 10; i++) { int[] dataMerge = SortCompare.GetRandomArrayInt(dataSize); int[] dataMergeBU = new int[dataSize]; dataMerge.CopyTo(dataMergeBU, 0); mergeSort.ClearArrayVisitCount(); mergeSortBU.ClearArrayVisitCount(); mergeSort.Sort(dataMerge); mergeSortBU.Sort(dataMergeBU); mergeResult[i] = mergeSort.GetArrayVisitCount(); mergeResultBU[i] = mergeSortBU.GetArrayVisitCount(); upperBound[i] = (int)(6 * dataSize * Math.Log(dataSize, 2)); dataSize *= 2; } // 绘图 Form2 plot = new Form2(); plot.Show(); Graphics graphics = plot.CreateGraphics(); // 获得绘图区矩形。 RectangleF rect = plot.ClientRectangle; float unitX = rect.Width / 10; float unitY = rect.Width / 10; // 添加 10% 边距作为文字区域。 RectangleF center = new RectangleF (rect.X + unitX, rect.Y + unitY, rect.Width - 2 * unitX, rect.Height - 2 * unitY); // 绘制坐标系。 graphics.DrawLine(Pens.Black, center.Left, center.Top, center.Left, center.Bottom); graphics.DrawLine(Pens.Black, center.Left, center.Bottom, center.Right, center.Bottom); graphics.DrawString("28000", plot.Font, Brushes.Black, rect.Location); graphics.DrawString("1024", plot.Font, Brushes.Black, center.Right, center.Bottom); graphics.DrawString("0", plot.Font, Brushes.Black, rect.Left, center.Bottom); // 初始化点。 PointF[] grayPoints = new PointF[10]; // 上限 PointF[] redPoints = new PointF[10]; // 自顶向下 PointF[] bluePoints = new PointF[10]; // 自底向上 unitX = center.Width / 11.0f; unitY = center.Height / 28000.0f; for (int i = 0; i < 10; i++) { grayPoints[i] = new PointF(center.Left + unitX * (i + 1), center.Bottom - (upperBound[i] * unitY) - 10); redPoints[i] = new PointF(center.Left + unitX * (i + 1), center.Bottom - (mergeResult[i] * unitY) - 10); bluePoints[i] = new PointF(center.Left + unitX * (i + 1), center.Bottom - (mergeResultBU[i] * unitY) - 10); } // 绘制点。 for (int i = 0; i < 10; i++) { graphics.FillEllipse(Brushes.Gray, new RectangleF(grayPoints[i], new SizeF(10, 10))); graphics.FillEllipse(Brushes.Red, new RectangleF(redPoints[i], new SizeF(10, 10))); graphics.FillEllipse(Brushes.Blue, new RectangleF(bluePoints[i], new Size(10, 10))); } graphics.Dispose(); } } }
2.2.7
解答
根据书本给出的命题 G 和命题 H（中文版 P173/176，英文版 P275/279），
比较次数的下限 C(N) = 1/2 * NlgN
N 和 lgN 都是单调递增且大于零的(N>1)，因此 C(N) 也是单调递增的
2.2.8
解答
修改后的算法对已经有序的情况做了优化
数组对半切分并排序后，
如果 a[mid] < a[mid + 1]（左半部分的最后一个元素小于右半部分的第一个元素）
那么我们可以直接合并数组，不需要再做多余的操作
现在的输入是一个已经排序的数组
算法唯一的比较发生在判断 a[mid] < a[mid + 1] 这个条件时
假定数组有 N 个元素
比较次数满足 T(N) = 2 * T(N / 2) + 1, T(1) = 0
转化为非递归形式即为：T(N) = cN / 2 + N - 1
其中 c 为任意正整数
2.2.9
解答
官方给出的归并排序实现中在 Sort 方法里初始化了 aux 数组。
源码见：https://algs4.cs.princeton.edu/22mergesort/Merge.java.html
C#实现和官方的实现非常类似，
首先定义只接受一个参数的公开 Sort 方法，在这个方法里面初始化 aux 数组。
/// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { T[] aux = new T[a.Length]; Sort(a, aux, 0, a.Length - 1); }
然后建立一个私有的递归 Sort 方法做实际的排序操作。
/// <summary> /// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T> { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; Sort(a, aux, lo, mid); Sort(a, aux, mid + 1, hi); Merge(a, aux, lo, mid, hi); }
代码
using System; namespace Merge { /// <summary> /// 归并排序类。 /// </summary> public class MergeSort : BaseSort { /// <summary> /// 默认构造函数。 /// </summary> public MergeSort() { } /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { T[] aux = new T[a.Length]; Sort(a, aux, 0, a.Length - 1); } /// <summary> /// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T> { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; Sort(a, aux, lo, mid); Sort(a, aux, mid + 1, hi); Merge(a, aux, lo, mid, hi); } /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">范围起点。</param> /// <param name="mid">范围中点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] a, T[] aux, int lo, int mid, int hi) where T : IComparable<T> { for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = aux[j]; j++; } else if (j > hi) { a[k] = aux[i]; i++; } else if (Less(aux[j], aux[i])) { a[k] = aux[j]; j++; } else { a[k] = aux[i]; i++; } } } } }
2.2.10
解答
官方同样给出了 java 实现，如下：
private static void merge(Comparable[] a, int lo, int mid, int hi) { for (int i = lo; i <= mid; i++) aux[i] = a[i]; for (int j = mid+1; j <= hi; j++) aux[j] = a[hi-j+mid+1]; int i = lo, j = hi; for (int k = lo; k <= hi; k++) if (less(aux[j], aux[i])) a[k] = aux[j--]; else a[k] = aux[i++]; }
C# 实现见代码部分。
代码
using System; using Merge; namespace _2._2._10 { /// <summary> /// 归并排序类。 /// </summary> public class MergeSort : BaseSort { /// <summary> /// 默认构造函数。 /// </summary> public MergeSort() { } /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { T[] aux = new T[a.Length]; Sort(a, aux, 0, a.Length - 1); } /// <summary> /// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T> { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; Sort(a, aux, lo, mid); Sort(a, aux, mid + 1, hi); Merge(a, aux, lo, mid, hi); } /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">范围起点。</param> /// <param name="mid">范围中点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] a, T[] aux, int lo, int mid, int hi) where T : IComparable<T> { // 前半部分升序复制 for (int k = lo; k <= mid; k++) { aux[k] = a[k]; } // 后半部分降序复制 for (int k = mid + 1; k <= hi; k++) { aux[k] = a[hi - k + mid + 1]; } // i 指向最左端，j 指向最右端 int i = lo, j = hi; for (int k = lo; k <= hi; k++) { if (Less(aux[j], aux[i])) { a[k] = aux[j]; j--; } else { a[k] = aux[i]; i++; } } } } }
2.2.11
解答
官方实现见：https://algs4.cs.princeton.edu/22mergesort/MergeX.java.html
在 MergeSortX 类里添加一个 CUTOFF 字段，排序时如果数组长度小于它则直接调用插入排序进行排序。
在调用归并方法前判断第一个有序数组的最后一个元素是否大于第二个有序数组的第一个元素，
如果大于的话就不需要调用归并了，直接首尾相接即可。
每次归并都需要两个数组，一个用于存放归并结果，这个数组中的内容是无关紧要的；
另一个则保存了归并前的数组，用于实际的归并过程。
归并结束后，前一个数组变成归并后的有序结果（也就是下一次归并时的「归并前数组」），后一个数组中的内容则不再有用。
我们可以看到这两个数组的角色在下一次归并时正好可以互换。
要注意的是，归并次数总是一个奇数（左侧归并+右侧归并+总归并），因此在第一次调用 Sort 方法时应该把 aux 和 a 互换传入。
代码
using System; namespace Merge { /// <summary> /// 优化后的归并排序类。 /// </summary> public class MergeSortX : BaseSort { /// <summary> /// 对小于 CUTOFF 的数组使用插入排序。 /// </summary> private static int CUTOFF = 7; /// <summary> /// 默认构造函数。 /// </summary> public MergeSortX() { } /// <summary> /// 设置启用插入排序的阈值，小于该阈值的数组将采用插入排序。 /// </summary> /// <param name="cutoff">新的阈值。</param> public void SetCutOff(int cutoff) => CUTOFF = cutoff; /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="src">原始数组。</param> /// <param name="dst">目标数组。</param> /// <param name="lo">范围起点。</param> /// <param name="mid">范围中点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] src, T[] dst, int lo, int mid, int hi) where T : IComparable<T> { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) dst[k] = src[j++]; else if (j > hi) dst[k] = src[i++]; else if (Less(src[j], src[i])) dst[k] = src[j++]; else dst[k] = src[i++]; } } /// <summary> /// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="src">原数组。</param> /// <param name="dst">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] src, T[] dst, int lo, int hi) where T : IComparable<T> { // 小于 CUTOFF 的数组调用插入排序 if (hi <= lo + CUTOFF) { InsertionSort insertion = new InsertionSort(); insertion.Sort(dst, lo, hi); return; } int mid = lo + (hi - lo) / 2; // 交换辅助数组和原数组 Sort(dst, src, lo, mid); Sort(dst, src, mid + 1, hi); // 已排序的数组直接合并 if (!Less(src[mid + 1], src[mid])) { Array.Copy(src, lo, dst, lo, hi - lo + 1); return; } Merge(src, dst, lo, mid, hi); } /// <summary> /// 利用优化后的归并排序对数组 a 排序。 /// </summary> /// <typeparam name="T">数组中的元素类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { T[] aux = new T[a.Length]; a.CopyTo(aux, 0); // aux 和 a 需要交换 Sort(aux, a, 0, a.Length - 1); } } }
2.2.12
解答
中文版的翻译比较难理解
实际上就是另一种归并排序的实现方式
先把数组分成若干个大小为 M 的块
对于每个块，用选择排序进行排序
随后遍历数组，将各个块归并起来
代码
using System; using Merge; namespace _2._2._12 { /// <summary> /// 归并排序类。 /// </summary> public class MergeSort : BaseSort { /// <summary> /// 默认构造函数。 /// </summary> public MergeSort() { } /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { Sort(a, 1); } /// <summary> /// 利用分块法进行归并排序。 /// </summary> /// <typeparam name="T">待排序的数组内容。</typeparam> /// <param name="a">待排序的数组。</param> /// <param name="M">分块大小。</param> public void Sort<T>(T[] a, int M) where T : IComparable<T> { int blockNum = a.Length / M; SelectionSort selection = new SelectionSort(); // 对块进行选择排序。 for (int i = 0; i < blockNum; i++) { int lo = i * M; int hi = (i + 1) * M - 1; selection.Sort(a, lo, hi); } // 将各个块合并。 for (int i = 0; i < blockNum - 1; i++) { Merge(a, 0, (i + 1) * M - 1, (i + 2) * M - 1); } } /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="lo">范围起点。</param> /// <param name="mid">范围中点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] a, int lo, int mid, int hi) where T : IComparable<T> { T[] aux = new T[hi - lo + 1]; for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = aux[j]; j++; } else if (j > hi) { a[k] = aux[i]; i++; } else if (Less(aux[j], aux[i])) { a[k] = aux[j]; j++; } else { a[k] = aux[i]; i++; } } } } }
2.2.13
解答
假设对三个数进行排序，这三个数是：35，10，17
三个数排序的决策树如下，结点代表比较对应位置上的数。
对于 35,10,17 来说，路径遵循右、左、左，最后得到的结果就是 2 3 1（10,17,35）。
我们可以发现决策树上的每一个叶子节点都代表一种排列顺序，对于 N 个数，叶子节点就有 N! 个
根据二叉树的性质，高度为 h 的二叉树最多有 2^h 个叶子节点
那么，对于 N 个数，决策树的高度 h 的最小值可以通过下面这个式子得出来
2^h >= n!
h >= log(n!)
因此可以得到决策树高度 h 的最小值是 log(n!)
接下来我们来计算平均路径长度
我们令函数 H(k) 代表有 k 个叶子节点的平衡决策树的所有路径长度之和
上例中 H(6) = 2 + 2 + 3 + 3 + 3 + 3 = 16
由于平衡决策树的性质，H(k) = 2H(k / 2) + k
（加上 k 的原因：左右子树的高度比整个树的高度小 1，因此每条路径的长度都必须加 1，总共多加了 k 次）
因此 H(k) = klogk
现在令 k = n!
H(n!) = n!log(n!)
由于每次排序时我们只经过某一条路径（上例中我们只经过了右、左、左这条路径）
而且每种路径的出现概率相等
因此平均比较次数应该为 H(n!) / n! = log(n!) = nlog(n)
证明完毕
2.2.14
解答
比较两个有序队列的第一个元素，取较小的一个出队并放入额外建立的队列中。
重复上述步骤直到两个队列都为空。
代码
/// <summary> /// 归并两个有序队列。输入队列将被清空。 /// </summary> /// <typeparam name="T">有序队列的元素类型。</typeparam> /// <param name="a">需要归并的队列。</param> /// <param name="b">需要归并的队列。</param> /// <returns>归并后的新队列。</returns> static Queue<T> Merge<T>(Queue<T> a, Queue<T> b) where T : IComparable<T> { Queue<T> sortedQueue = new Queue<T>(); while (!a.IsEmpty() && !b.IsEmpty()) { if (a.Peek().CompareTo(b.Peek()) < 0) sortedQueue.Enqueue(a.Dequeue()); else sortedQueue.Enqueue(b.Dequeue()); } while (!a.IsEmpty()) sortedQueue.Enqueue(a.Dequeue()); while (!b.IsEmpty()) sortedQueue.Enqueue(b.Dequeue()); return sortedQueue; }
2.2.15
解答
程序思路题目已经给出，按照题意实现即可。
Merge 方法可以直接使用前一题的实现。
代码
using System; namespace _2._2._15 { /// <summary> /// 利用队列归并实现的自底向上的归并排序。 /// </summary> class MergeSortQueue { /// <summary> /// 默认构造函数。 /// </summary> public MergeSortQueue() { } /// <summary> /// 利用队列归并进行自底向上的归并排序。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">需要排序的数组。</param> public void Sort<T>(T[] a) where T : IComparable<T> { Queue<Queue<T>> queueList = new Queue<Queue<T>>(); for (int i = 0; i < a.Length; i++) { Queue<T> temp = new Queue<T>(); temp.Enqueue(a[i]); queueList.Enqueue(temp); } while (queueList.Size() != 1) { int times = queueList.Size() / 2; for (int i = 0; i < times; i++) { Queue<T> A = queueList.Dequeue(); Queue<T> B = queueList.Dequeue(); queueList.Enqueue(Merge(A, B)); } } Queue<T> result = queueList.Dequeue(); for (int i = 0; i < a.Length; i++) { a[i] = result.Dequeue(); } } /// <summary> /// 归并两个有序队列。输入队列将被清空。 /// </summary> /// <typeparam name="T">有序队列的元素类型。</typeparam> /// <param name="a">需要归并的队列。</param> /// <param name="b">需要归并的队列。</param> /// <returns>归并后的新队列。</returns> public static Queue<T> Merge<T>(Queue<T> a, Queue<T> b) where T : IComparable<T> { Queue<T> sortedQueue = new Queue<T>(); while (!a.IsEmpty() && !b.IsEmpty()) { if (a.Peek().CompareTo(b.Peek()) < 0) sortedQueue.Enqueue(a.Dequeue()); else sortedQueue.Enqueue(b.Dequeue()); } while (!a.IsEmpty()) sortedQueue.Enqueue(a.Dequeue()); while (!b.IsEmpty()) sortedQueue.Enqueue(b.Dequeue()); return sortedQueue; } } }
2.2.16
解答
自然归并排序的一个示例如下图所示：
基本过程和自底向上的归并排序类似，只是每次归并的块大小不一定相同。
时间分析
随着有序块的变大，排序耗时会缩短，但增长的数量级会变高（归并的平均块大小变大了）。
代码
using System; using System.Diagnostics; namespace Merge { /// <summary> /// 自然的归并排序。 /// </summary> public class MergeSortNatural : BaseSort { /// <summary> /// 默认构造函数。 /// </summary> public MergeSortNatural() { } /// <summary> /// 利用自然的归并排序进行自底向上的排序。 /// </summary> /// <typeparam name="T">用于排序的元素类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { T[] aux = new T[a.Length]; while (true) { // 找到第一个块 int lo = 0; int mid = FindBlock(lo, a) - 1; if (mid == a.Length - 1) break; while (mid < a.Length - 1) { int hi = FindBlock(mid + 1, a) + mid; Merge(lo, mid, hi, a, aux); lo = hi + 1; mid = FindBlock(lo, a) + lo - 1; } } Debug.Assert(IsSorted(a)); } /// <summary> /// 将两个块归并。 /// </summary> /// <typeparam name="T">数组的元素类型。</typeparam> /// <param name="lo">第一个块的开始下标。</param> /// <param name="mid">第一个块的结束下标（第二个块的开始下标 - 1）。</param> /// <param name="hi">第二个块的结束下标。</param> /// <param name="a">需要归并的数组。</param> /// <param name="aux">辅助数组。</param> private void Merge<T>(int lo, int mid, int hi, T[] a, T[] aux) where T : IComparable<T> { for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = aux[j]; j++; } else if (j > hi) { a[k] = aux[i]; i++; } else if (Less(aux[j], aux[i])) { a[k] = aux[j]; j++; } else { a[k] = aux[i]; i++; } } } /// <summary> /// 获取下一个有序块。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="lo">查找起点。</param> /// <param name="a">用于查找的数组。</param> /// <returns>块的大小。</returns> private int FindBlock<T>(int lo, T[] a) where T : IComparable<T> { int size = 1; for (int i = lo; i < a.Length - 1; i++) { if (Less(a[i], a[i + 1]) || a[i].Equals(a[i + 1])) size++; else break; } return size; } } }
2.2.17
解答
排序方式和 2.2.16 十分类似，不再赘述，这里介绍一下归并方法。
如 gif 图所示，先把要归并的两个链表拆出来，随后确定表头位置，然后进行归并即可。
归并结束后返回 first。
结果分析如下图所示：
随着有序部分的增加，对于相同大小的数组自然归并排序的耗时会缩短。
对于有序部分相同的情况，随着数组大小的倍增，耗时呈现了O(nlogn)的趋势。
代码
using System; using System.Diagnostics; using Merge; namespace _2._2._17 { /// <summary> /// 自然的归并排序。 /// </summary> public class MergeSortNatural : BaseSort { /// <summary> /// 默认构造函数。 /// </summary> public MergeSortNatural() { } /// <summary> /// 利用自然的归并排序进行自底向上的排序。 /// </summary> /// <typeparam name="T">用于排序的元素类型。</typeparam> /// <param name="a">需要排序的数组。</param> public override void Sort<T>(T[] a) { T[] aux = new T[a.Length]; while (true) { // 找到第一个块 int lo = 0; int mid = FindBlock(lo, a) - 1; if (mid == a.Length - 1) break; while (mid < a.Length - 1) { int hi = FindBlock(mid + 1, a) + mid; Merge(lo, mid, hi, a, aux); lo = hi + 1; mid = FindBlock(lo, a) + lo; } } Debug.Assert(IsSorted(a)); } /// <summary> /// 利用自然的归并排序将链表排序。 /// </summary> /// <typeparam name="T">链表元素类型。</typeparam> /// <param name="a">等待排序的链表。</param> public void Sort<T>(LinkedList<T> a) where T : IComparable<T> { while (true) { // 找到第一个块 Node<T> lo = a.GetFirst(); Node<T> mid = FindBlock(lo); if (mid.next == null) break; while (mid.next != null) { Node<T> hi = FindBlock(mid.next); if (lo == a.GetFirst()) a.SetFirst(Merge(lo, mid, hi)); else lo.next = Merge(lo.next, mid, hi); // 跳到表尾 if (Less(hi.item, mid.item)) lo = mid; else lo = hi; if (lo.next != null) mid = FindBlock(lo.next); } } } /// <summary> /// 将两个块归并。 /// </summary> /// <typeparam name="T">数组的元素类型。</typeparam> /// <param name="lo">第一个块的开始下标。</param> /// <param name="mid">第一个块的结束下标（第二个块的开始下标 - 1）。</param> /// <param name="hi">第二个块的结束下标。</param> /// <param name="a">需要归并的数组。</param> /// <param name="aux">辅助数组。</param> private void Merge<T>(int lo, int mid, int hi, T[] a, T[] aux) where T : IComparable<T> { for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = aux[j]; j++; } else if (j > hi) { a[k] = aux[i]; i++; } else if (Less(aux[j], aux[i])) { a[k] = aux[j]; j++; } else { a[k] = aux[i]; i++; } } } /// <summary> /// 将两个有序链表块归并，返回新的表头。 /// </summary> /// <typeparam name="T">链表元素类型。</typeparam> /// <param name="lo">第一个有序块起点。</param> /// <param name="mid">第一个有序块终点（第二个有序块起点的前驱）。</param> /// <param name="hi">第二个有序块的终点。</param> /// <returns>新的表头。</returns> private Node<T> Merge<T>(Node<T> lo, Node<T> mid, Node<T> hi) where T : IComparable<T> { Node<T> after = hi.next; // 要合并的两个块之后的元素 Node<T> first = null; Node<T> i = lo; // 链表1 Node<T> j = mid.next; // 链表2 // 切割链表 mid.next = null; hi.next = null; Node<T> current = null; // 决定新的表头 if (Less(i.item, j.item)) { current = i; i = i.next; } else { current = j; j = j.next; } first = current; // 归并表 while (i != null && j != null) { if (Less(i.item, j.item)) { current.next = i; i = i.next; current = current.next; } else { current.next = j; j = j.next; current = current.next; } } if (i == null) current.next = j; else current.next = i; // 连接表尾（链表 1 的尾部或者链表 2 的尾部） if (mid.next == null) mid.next = after; else hi.next = after; return first; } /// <summary> /// 获取下一个有序块。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="lo">查找起点。</param> /// <param name="a">用于查找的数组。</param> /// <returns>块的大小。</returns> private int FindBlock<T>(int lo, T[] a) where T : IComparable<T> { int size = 1; for (int i = lo; i < a.Length - 1; i++) { if (Less(a[i], a[i + 1]) || a[i].Equals(a[i + 1])) size++; else break; } return size; } /// <summary> /// 获取链表的下一个有序块。 /// </summary> /// <typeparam name="T">链表的元素类型。</typeparam> /// <param name="lo">查找的起始结点。</param> /// <returns>有序块的最后一个元素结点。</returns> private Node<T> FindBlock<T>(Node<T> lo) where T : IComparable<T> { Node<T> hi = lo; while (hi.next != null) { if (Less(hi.item, hi.next.item) || hi.item.Equals(hi.next.item)) hi = hi.next; else break; } return hi; } } }
2.2.18
解答
可以在用归并排序的方法做。
将归并时取两边较小的元素改为随机取一侧的值，即可实现打乱的效果。
算法的分析和普通归并排序一致，满足题目要求。
代码
分治法打乱链表的实现。
using System; namespace _2._2._18 { /// <summary> /// 分治法打乱链表。
/// </summary> public class MergeShuffle { /// <summary> /// 默认构造函数。 /// </summary> public MergeShuffle() { } /// <summary> /// 利用分治法打乱链表。 /// </summary> /// <typeparam name="T">链表元素类型。</typeparam> /// <param name="a">等待打乱的链表。</param> public void Shuffle<T>(LinkedList<T> a) { int blockLen = 1; Random random = new Random(); while (blockLen <= a.Size()) { // 找到第一个块 Node<T> lo = a.GetFirst(); Node<T> mid = FindBlock(lo, blockLen); if (mid.next == null) break; while (mid.next != null) { Node<T> hi = FindBlock(mid.next, blockLen); Node<T>[] result; if (lo == a.GetFirst()) { result = Merge(lo, mid, hi, random); a.SetFirst(result[0]); } else { result = Merge(lo.next, mid, hi, random); lo.next = result[0]; } // 跳到表尾 lo = result[1]; if (lo.next != null) mid = FindBlock(lo.next, blockLen); else mid = lo; } blockLen *= 2; } } /// <summary> /// 将两个有序链表块随机归并，返回新的表头。 /// </summary> /// <typeparam name="T">链表元素类型。</typeparam> /// <param name="lo">第一个块起点。</param> /// <param name="mid">第一个块终点（第二个块起点的前驱）。</param> /// <param name="hi">第二个块的终点。</param> /// <returns>新的表头。</returns> private Node<T>[] Merge<T>(Node<T> lo, Node<T> mid, Node<T> hi, Random random) { Node<T> after = hi.next; // 要合并的两个块之后的元素 Node<T> first = null; Node<T>[] result = new Node<T>[2]; Node<T> i = lo; // 链表1 Node<T> j = mid.next; // 链表2 // 切割链表 mid.next = null; hi.next = null; Node<T> current = null; // 决定新的表头 if (random.NextDouble() >= 0.5) { current = i; i = i.next; } else { current = j; j = j.next; } first = current; // 归并表 while (i != null && j != null) { if (random.NextDouble() >= 0.5) { current.next = i; i = i.next; current = current.next; } else { current.next = j; j = j.next; current = current.next; } } if (i == null) current.next = j; else current.next = i; // 连接表尾（链表 1 的尾部或者链表 2 的尾部） if (mid.next == null) { mid.next = after; result[1] = mid; } else { hi.next = after; result[1] = hi; } result[0] = first; return result; } /// <summary> /// 获取从指定位置开始定长的链表。 /// </summary> /// <typeparam name="T">链表的元素类型。</typeparam> /// <param name="lo">链表的起始结点。</param> /// <param name="length">需要获取的链表长度。</param> /// <returns>结果链表的最后一个元素结点。</returns> private Node<T> FindBlock<T>(Node<T> lo, int length) { Node<T> hi = lo; for (int i = 0; i < length - 1 && hi.next != null; i++) { hi = hi.next; } return hi; } } }
2.2.19
解答
官方实现：https://algs4.cs.princeton.edu/22mergesort/Inversions.java.html
事实上只要在归并排序的时候统计 Less(aux[j], aux[i]) 满足的次数即可，这个次数就是我们要的值。
代码
using System; using Merge; namespace _2._2._19 { /// <summary> /// 归并排序类。 /// </summary> public class MergeSort : BaseSort { public int Counter = 0; /// <summary> /// 默认构造函数。 /// </summary> public MergeSort() { } /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { T[] aux = new T[a.Length]; Sort(a, aux, 0, a.Length - 1); } /// <summary> /// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T> { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; Sort(a, aux, lo, mid); Sort(a, aux, mid + 1, hi); Merge(a, aux, lo, mid, hi); } /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">范围起点。</param> /// <param name="mid">范围中点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] a, T[] aux, int lo, int mid, int hi) where T : IComparable<T> { for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = aux[j]; j++; } else if (j > hi) { a[k] = aux[i]; i++; } else if (Less(aux[j], aux[i])) { a[k] = aux[j]; this.Counter += mid - i + 1; // 统计逆序对数 j++; } else { a[k] = aux[i]; i++; } } } } }
2.2.20
解答
官方实现：https://algs4.cs.princeton.edu/22mergesort/Merge.java.html
把 Sort 方法中传入的 a 数组换成一个 index 数组，将 Merge 方法中的判断改为 Less(a[aux[j]], a[aux[i]]) 即可。
代码
using System; using Merge; namespace _2._2._20 { /// <summary> /// 归并排序类。 /// </summary> public class MergeSort : BaseSort { /// <summary> /// 默认构造函数。 /// </summary> public MergeSort() { } /// <summary> /// 利用归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public int[] IndexSort<T>(T[] a) where T : IComparable<T> { int[] aux = new int[a.Length]; int[] index = new int[a.Length]; for (int i = 0; i < a.Length; i++) { index[i] = i; } Sort(a, index, aux, 0, a.Length - 1); return index; } /// <summary> /// 自顶向下地对数组指定范围内进行归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] a, int[] index, int[] aux, int lo, int hi) where T : IComparable<T> { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; Sort(a, index, aux, lo, mid); Sort(a, index, aux, mid + 1, hi); Merge(a, index, aux, lo, mid, hi); } /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">范围起点。</param> /// <param name="mid">范围中点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] a, int[] index, int[] aux, int lo, int mid, int hi) where T : IComparable<T> { for (int k = lo; k <= hi; k++) { aux[k] = index[k]; } int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { index[k] = aux[j]; j++; } else if (j > hi) { index[k] = aux[i]; i++; } else if (Less(a[aux[j]], a[aux[i]])) { index[k] = aux[j]; j++; } else { index[k] = aux[i]; i++; } } } public override void Sort<T>(T[] a) { throw new NotImplementedException(); } } }
2.2.21
解答
对三份列表进行归并排序（O(nlogn)），随后遍历一遍其中的一份表，
用二分查找检查在其余两个表中是否存在相同的姓名（O(nlogn)）
代码
using System; using Merge; namespace _2._2._21 { /* * 2.2.21 * * 一式三份。 * 给定三个列表， * 每个列表中包含 N 个名字， * 编写一个线性对数级别的算法来判定三份列表中是否含有公共的名字， * 如果有，返回第一个被找到的这种名字。 * */ class Program { static void Main(string[] args) { string[] name1 = new string[] { "Noah", "Liam", "Jacob", "Mason" }; string[] name2 = new string[] { "Sophia", "Emma", "Mason", "Ava" }; string[] name3 = new string[] { "Mason", "Marcus", "Alexander", "Ava" }; MergeSort mergeSort = new MergeSort(); mergeSort.Sort(name1); mergeSort.Sort(name2); mergeSort.Sort(name3); for (int i = 0; i < name1.Length; i++) { if (BinarySearch(name1[i], name2, 0, name1.Length) != -1 && BinarySearch(name1[i], name3, 0, name1.Length) != -1) { Console.WriteLine(name1[i]); break; } } } /// <summary> /// 二分查找，返回目标元素的下标，没有结果则返回 -1。 /// </summary> /// <typeparam name="T">查找的元素类型。</typeparam> /// <param name="key">要查找的目标值。</param> /// <param name="array">用于查找的目标范围。</param> /// <param name="lo">查找的起始下标。</param> /// <param name="hi">查找的终止下标。</param> /// <returns>找到则返回元素下标，否则返回 -1。</returns> static int BinarySearch<T>(T key, T[] array, int lo, int hi) where T : IComparable<T> { while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (array[mid].Equals(key)) return mid; else if (array[mid].CompareTo(key) < 0) lo = mid + 1; else hi = mid - 1; } return -1; } } }
2.2.22
解答
增长数量级为O(nlogn)。
代码
using System; using System.Diagnostics; namespace Merge { /// <summary> /// 三向归并排序。 /// </summary> public class MergeSortThreeWay : BaseSort { /// <summary> /// 默认构造函数。 /// </summary> public MergeSortThreeWay() { } /// <summary> /// 利用三项归并排序将数组按升序排序。 /// </summary> /// <typeparam name="T">数组中的元素类型。</typeparam> /// <param name="a">待排序的数组。</param> public override void Sort<T>(T[] a) { T[] aux = new T[a.Length]; Sort(a, aux, 0, a.Length - 1); Debug.Assert(IsSorted(a)); } /// <summary> /// 自顶向下地对数组指定范围内进行三向归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T> { if (hi <= lo) // 小于或等于一个元素 return; int lmid = lo + (hi - lo) / 3; int rmid = hi - (hi - lo) / 3; Sort(a, aux, lo, lmid); Sort(a, aux, lmid + 1, rmid); Sort(a, aux, rmid + 1, hi); Merge(a, aux, lo, lmid, rmid, hi); } /// <summary> /// 返回两个元素中较小的那个。 /// </summary> /// <typeparam name="T">比较的元素类型。</typeparam> /// <param name="a">用于比较的元素。</param> /// <param name="b">用于比较的元素。</param> /// <returns>较小的元素。</returns> private T Min<T>(T a, T b) where T : IComparable<T> { if (Less(a, b)) return a; return b; } /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">范围起点。</param> /// <param name="lmid">范围三分之一点。</param> /// <param name="rmid">范围三分之二点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] a, T[] aux, int lo, int lmid, int rmid, int hi) where T : IComparable<T> { for (int l = lo; l <= hi; l++) { aux[l] = a[l]; } int i = lo, j = lmid + 1, k = rmid + 1; for (int l = lo; l <= hi; l++) { int flag = 0; if (i > lmid) flag += 1; if (j > rmid) flag += 10; if (k > hi) flag += 100; switch (flag) { case 0: // 三个数组都还没有取完 T min = Min(aux[i], Min(aux[j], aux[k])); if (min.Equals(aux[i])) a[l] = aux[i++]; else if (min.Equals(aux[j])) a[l] = aux[j++]; else a[l] = aux[k++]; break; case 1: // 只有第一个数组取完了 if (Less(aux[j], aux[k])) a[l] = aux[j++]; else a[l] = aux[k++]; break; case 10: // 只有第二个数组取完了 if (Less(aux[i], aux[k])) a[l] = aux[i++]; else a[l] = aux[k++]; break; case 100: // 只有第三个数组取完了 if (Less(aux[i], aux[j])) a[l] = aux[i++]; else a[l] = aux[j++]; break; case 11: // 第一、二个数组取完了 a[l] = aux[k++]; break; case 101: // 第一、三个数组取完了 a[l] = aux[j++]; break; case 110: // 第二、三个数组取完了 a[l] = aux[i++]; break; } } } } }
2.2.23
解答
阈值合适时，大约会有10%的性能提升。
阈值在 10 以下都是比较合适的。
代码
using System; using Merge; namespace _2._2._23 { /* * 2.2.23 * * 改进。 * 用实验评估正文中所提到的归并排序的三项改进（请见练习 2.2.11）的效果， * 并比较正文中实现的归并排序和练习 2.2.10 所实现的归并排序之间的性能。 * 根据经验给出应该在何时为子数组切换到插入排序。 * */ class Program { static void Main(string[] args) { MergeSort mergeSort = new MergeSort(); MergeSortX mergeSortX = new MergeSortX(); MergeSortUnstable mergeSortUnstable = new MergeSortUnstable(); int n = 1000000; int cutoff = 2; int trialTime = 4; Console.WriteLine("归并排序改进前与改进后的比较："); Console.WriteLine("数组 耗时1 耗时2 阈值 比率"); for (int i = 0; i < 20; i++) { double mergeSortTime = 0; double mergeSortXTime = 0; mergeSortX.SetCutOff(cutoff); for (int j = 0; j < trialTime; j++) { int[] a = SortCompare.GetRandomArrayInt(n); int[] b = new int[a.Length]; a.CopyTo(b, 0); mergeSortTime += SortCompare.Time(mergeSort, a); mergeSortXTime += SortCompare.Time(mergeSortX, b); } mergeSortTime /= trialTime; mergeSortXTime /= trialTime; Console.WriteLine(n + " " + mergeSortTime + " " + mergeSortXTime + " " + cutoff + " " + mergeSortTime / mergeSortXTime); cutoff++; } n = 100000; Console.WriteLine("稳定归并排序与不稳定版本的比较："); Console.WriteLine("数组 耗时1 耗时2 比率"); for (int i = 0; i < 6; i++) { double mergeSortTime = 0; double mergeSortUnstableTime = 0; for (int j = 0; j < trialTime; j++) { int[] a = SortCompare.GetRandomArrayInt(n); int[] b = new int[a.Length]; a.CopyTo(b, 0); mergeSortTime += SortCompare.Time(mergeSort, a); mergeSortUnstableTime += SortCompare.Time(mergeSortUnstable, b); } mergeSortTime /= trialTime; mergeSortUnstableTime /= trialTime; Console.WriteLine(n + " " + mergeSortTime + " " + mergeSortUnstableTime + " " + mergeSortTime / mergeSortUnstableTime); n *= 2; } } } }
2.2.24
解答
约为 lgN 次
代码
using System; using Merge; namespace _2._2._24 { /* * 2.2.24 * * 改进的有序测试。 * 在实验中用大型随机数组评估练习 2.2.8 所做的修改的效果。 * 根据经验用 N（被排序的原始数组的大小）的函数描述条件语句 * （a[mid] <= a[mid + 1]）成立（无论数组是否有序）的次数。 * */ class Program { static void Main(string[] args) { MergeSortX mergeSortX = new MergeSortX(); int n = 10000; int trialTimes = 10; Console.WriteLine("数组 平均命中次数"); for (int i = 0; i < 4; i++) { int avgHit = 0; for (int j = 0; j < trialTimes; j++) { mergeSortX.ResetHitTime(); int[] a = SortCompare.GetRandomArrayInt(n); mergeSortX.Sort(a); avgHit += mergeSortX.GetHitTime(); } Console.WriteLine(n + " " + avgHit / trialTimes); n *= 10; } } } }
2.2.25
解答
事实上 k 的取值无关紧要，实验也证明了这一点。
算法大致可以分为以下几个步骤
首先将数组划为 k 份，用一个数组 mids 记录这 k 个子数组的分割位置
随后递归的调用 Sort 方法，将这 k 个子数组排序
随后将这 k 个子数组归并，
每次归并时遍历取 k 个子数组中值最小的一个，然后对应子数组的指示器 + 1
上面这一步是 O(k) 的，可以用堆或者败者树优化为对数级别
代码
using System; using System.Diagnostics; namespace Merge { /// <summary> /// k 路归并排序。 /// </summary> public class MergeSortKWay : BaseSort { /// <summary> /// 同时归并的数组数目。 /// </summary> public int K { get; set; } /// <summary> /// 默认构造函数。 /// </summary> public MergeSortKWay() { this.K = 2; } /// <summary> /// 用 k 向归并排序对数组 a 进行排序。 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="a"></param> /// <exception cref="ArgumentOutOfRangeException">数组长度小于 K 值时抛出异常。</exception> public override void Sort<T>(T[] a) { if (this.K > a.Length) throw new ArgumentOutOfRangeException("数组长度不能小于 K 值！"); T[] aux = new T[a.Length]; Sort(a, aux, 0, a.Length - 1); Debug.Assert(IsSorted(a)); } /// <summary> /// 自顶向下地对数组指定范围内进行 k 向归并排序，需要辅助数组。 /// </summary> /// <typeparam name="T">需要排序的元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">排序范围起点。</param> /// <param name="hi">排序范围终点。</param> private void Sort<T>(T[] a, T[] aux, int lo, int hi) where T : IComparable<T> { if (hi <= lo) // 小于或等于一个元素 return; int[] mids = new int[this.K - 1]; int steps = (hi - lo) / this.K; mids[0] = lo + steps; for (int i = 1; i < this.K - 1; i++) { mids[i] = mids[i - 1] + steps; if (mids[i] > hi) // 防止溢出 mids[i] = hi; } Sort(a, aux, lo, mids[0]); for (int i = 1; i < this.K - 1; i++) { Sort(a, aux, mids[i - 1] + 1, mids[i]); } Sort(a, aux, mids[this.K - 2] + 1, hi); Merge(a, aux, lo, mids, hi); } /// <summary> /// 将指定范围内的元素归并。 /// </summary> /// <typeparam name="T">数组元素类型。</typeparam> /// <param name="a">原数组。</param> /// <param name="aux">辅助数组。</param> /// <param name="lo">范围起点。</param> /// <param name="mids">范围中间点。</param> /// <param name="hi">范围终点。</param> private void Merge<T>(T[] a, T[] aux, int lo, int[] mids, int hi) where T : IComparable<T> { for (int l = lo; l <= hi; l++) { aux[l] = a[l]; } int[] pointers = new int[this.K]; // 标记每个数组的当前归并位置 pointers[0] = lo; // 开始时归并位置处于每个子数组的起始 for (int i = 1; i < this.K; i++) { pointers[i] = mids[i - 1] + 1; } // 开始归并 for (int i = lo; i <= hi; i++) { // 找到最小值 T min; int minPointerIndex = 0; bool isInit = true; if (pointers[this.K - 1] > hi) { min = default(T); // 初始化以避免编译错误 } else { min = aux[pointers[this.K - 1]]; minPointerIndex = this.K - 1; isInit = false; } for (int j = 0; j < this.K - 1; j++) { if (pointers[j] > mids[j]) // 当前数组已经用完 continue; if (isInit) // 第一次赋值 { isInit = false; min = aux[pointers[j]]; minPointerIndex = j; continue; } if (Less(aux[pointers[j]], min)) { min = aux[pointers[j]]; minPointerIndex = j; } } // 将最小值赋给归并数组，对应子数组的归并位置+1 a[i] = min; pointers[minPointerIndex]++; } } } }
2.2.26
解答
差距还是比较明显的，由于 Merge 会调用多次，而用于启动递归的 Sort 方法只会调用一次。
代码
using System; using Merge; namespace _2._2._26 { /* * 2.2.26 * * 创建数组。 * 使用 SortCompare 粗略比较在你的计算机上 * 在 merge() 中和在 sort() 中创建 aux[] 的性能差异。 * */ class Program { static void Main(string[] args) { AuxInSortMergeSort auxInSort = new AuxInSortMergeSort(); AuxInMergeMergeSort auxInMerge = new AuxInMergeMergeSort(); int[] data1 = SortCompare.GetRandomArrayInt(100000); int[] data2 = new int[data1.Length]; data1.CopyTo(data2, 0); Console.WriteLine("在Sort中创建aux[] " + SortCompare.Time(auxInSort, data1) + "ms"); Console.WriteLine("在Merge中创建aux[] " + SortCompare.Time(auxInMerge, data2) + "ms"); } } }
2.2.27
解答
大致上会是一个对数函数，用 Excel 做了简单的拟合。
代码
using System; using Merge; namespace _2._2._27 { /* * 2.2.27 * * 子数组长度。 * 用归并将大型随机数组排序， * 根据经验用 N （某次归并时两个子数组的长度之和） * 的函数估计当一个子数组用尽时另一个子数组的平均长度。 * */ class Program { static void Main(string[] args) { int arraySize = 1000000; NotifiedMergeSort sort = new NotifiedMergeSort(arraySize); for (int i = 0; i < 100; i++) { int[] data = SortCompare.GetRandomArrayInt(arraySize); sort.Sort(data); } Console.WriteLine("n rest times"); for (int i = 0; i < sort.NArraySize.Length; i++) { if (sort.NArraySize[i] != 0) Console.WriteLine(i + " " + sort.NArraySize[i] / sort.NArraySizeTime[i] + " " + sort.NArraySizeTime[i]); } // 大致上是一个对数函数 } } }
2.2.28
解答
自底向上会快一些，省去了递归过程中函数重复调用的时间。
代码
using System; using Merge; namespace _2._2._28 { /* * 2.2.28 * * 自顶向下和自底向上。 * 对于 N=10^3、10^4、10^5 和 10^6， * 使用 SortCompare 比较自顶向下和自底向上的归并排序的性能。 * */ class Program { static void Main(string[] args) { int n = 1000; MergeSort topBottomMergeSort = new MergeSort(); MergeSortBU bottomUpMergeSort = new MergeSortBU(); int trialTimes = 100; for (int i = 0; i < 4; i++) { Console.Write("数组大小：" + n + " "); int time1 = 0, time2 = 0; for (int j = 0; j < trialTimes; j++) { double[] data1 = SortCompare.GetRandomArrayDouble(n); double[] data2 = new double[n]; data1.CopyTo(data2, 0); time1 += (int)SortCompare.Time(topBottomMergeSort, data1); time2 += (int)SortCompare.Time(bottomUpMergeSort, data2); } Console.WriteLine("自顶向下：" + time1 / trialTimes + "ms 自底向上：" + time2 / trialTimes + "ms"); n *= 10; } } } }
2.2.29
解答
完全有序时只需要一次归并（直接输出），
逆序时需要 n - 1 次归并（退化为插入排序），
平均需要 n/2 次归并。
所以分别需要 500，500000，500000000 次归并。
span>Insertion: " + SortCompare.Time(insertionSort, arrayInsertion)); Console.WriteLine("Selection: " + SortCompare.Time(selectionSort, arraySelection)); Console.WriteLine("Shell: " + SortCompare.Time(shellSort, arrayShell)); // 泊松分布 arrayInsertion = SortCompare.GetPossionDistributionArray(n); arrayInsertion.CopyTo(arraySelection, 0); arrayInsertion.CopyTo(arrayShell, 0); Console.WriteLine("Poission Distribution:"); Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion)); Console.WriteLine("Selection: " + SortCompare.Time(selectionSort, arraySelection)); Console.WriteLine("Shell: " + SortCompare.Time(shellSort, arrayShell)); // 几何分布 arrayInsertion = SortCompare.GetGeometricDistributionArray(n, 0.3); arrayInsertion.CopyTo(arraySelection, 0); arrayInsertion.CopyTo(arrayShell, 0); Console.WriteLine("Geometric Distribution:"); Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion)); Console.WriteLine("Selection: " + SortCompare.Time(selectionSort, arraySelection)); Console.WriteLine("Shell: " + SortCompare.Time(shellSort, arrayShell)); // 离散分布 arrayInsertion = SortCompare.GetDiscretDistributionArray(n, new double[] { 0.1, 0.2, 0.3, 0.1, 0.1, 0.1, 0.1 }); arrayInsertion.CopyTo(arraySelection, 0); arrayInsertion.CopyTo(arrayShell, 0); Console.WriteLine("Discret Distribution:"); Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion)); Console.WriteLine("Selection: " + SortCompare.Time(selectionSort, arraySelection)); Console.WriteLine("Shell: " + SortCompare.Time(shellSort, arrayShell)); } } }
2.1.36
解答
最后结果：
代码
using System; using Sort; namespace _2._1._36 { /* * 2.1.36 * * 不均匀的数据。 * 编写一个测试用例， * 生成不均匀的测试数据，包括： * 一半数据是 0，一半数据是 1 * 一半数据是 0，1/4 是 1，1/4 是 2，以此类推 * 一半数据是 0，一半是随机 int 值。 * 评估并验证这些输入数据对本节讨论的算法的性能的影响。 * */ class Program { // 选择排序的耗时与输入值的内容无关，不受影响。 // 对于插入排序，以上几种情况都是重复值较多的情况，插入排序的速度会加快。 // 希尔排序本质上也是插入排序，因此也会更快一些。 static void Main(string[] args) { int n = 10000; InsertionSort insertionSort = new InsertionSort(); SelectionSort selectionSort = new SelectionSort(); ShellSort shellSort = new ShellSort(); int[] arrayInsertion = new int[n]; int[] arraySelection = new int[n]; int[] arrayShell = new int[n]; // 对照，完全随机 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.TimeRandomInput(shellSort, n, 1)); Console.WriteLine(); // 一半是 0 一半是 1 arrayInsertion = HalfZeroHalfOne(n); arrayInsertion.CopyTo(arraySelection, 0); arrayInsertion.CopyTo(arrayShell, 0); Console.WriteLine("half 0 and half 1"); Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayInsertion)); Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, arraySelection)); Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, arrayShell)); Console.WriteLine(); // 一半是 0， 1/4 是 1， 1/8 是 2…… arrayInsertion = HalfAndHalf(n); arrayInsertion.CopyTo(arraySelection, 0); arrayShell.CopyTo(arrayShell, 0); Console.WriteLine("half and half and half ..."); Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayInsertion)); Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, arraySelection)); Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, arrayShell)); Console.WriteLine(); // 一半是 0，一半是随机 int 值 arrayInsertion = HalfZeroHalfRandom(n); arrayInsertion.CopyTo(arraySelection, 0); arrayShell.CopyTo(arrayShell, 0); Console.WriteLine("half 0 half random"); Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayInsertion)); Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, arraySelection)); Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, arrayShell)); } /// <summary> /// 获取一半是 0 一半是 1 的随机 <see cref="int"/> 数组。 /// </summary> /// <param name="n">数组大小。</param> /// <returns>一半是 0 一半是 1 的 <see cref="int"/>数组。</returns> static int[] HalfZeroHalfOne(int n) { int[] result = new int[n]; Random random = new Random(); for (int i = 0; i < n; i++) { if (random.NextDouble() >= 0.5) { result[i] = 0; } else { result[i] = 1; } } return result; } /// <summary> /// 生成 1/2 为 0， 1/4 为 1， 1/8 为 2 …… 的 <see cref="int"/> 数组。 /// </summary> /// <param name="n">数组长度。</param> /// <returns>1/2 为 0， 1/4 为 1， 1/8 为 2 …… 的 <see cref="int"/> 数组。</returns> static int[] HalfAndHalf(int n) { int[] array = new int[n]; HalfIt(0, 0, n / 2, array); Shuffle(array); return array; } /// <summary> /// 递归生成 1/2 为 0， 1/4 为 1， 1/8 为 2 …… 的 <see cref="int"/> 数组。 /// </summary> /// <param name="start">填充起点。</param> /// <param name="number">起始编号。</param> /// <param name="length">填充长度</param> /// <param name="array">用于填充的数组。</param> /// <returns>一个 <see cref="int"/> 数组。</returns> static int[] HalfIt(int start, int number, int length, int[] array) { if (length == 0) return array; for (int i = 0; i < length; i++) { array[start + i] = number; } return HalfIt(start + length, number + 1, length / 2, array); } /// <summary> /// 生成一半是 0 一半是随机整数的 <see cref="int"/> 数组。 /// </summary> /// <param name="n">数组大小。</param> /// <returns>生成一半是 0 一半是随机整数的 <see cref="int"/> 数组。</returns> static int[] HalfZeroHalfRandom(int n) { int[] array = new int[n]; Random random = new Random(); for (int i = 0; i < n / 2; i++) { array[i] = 0; } for (int i = n / 2; i < n; i++) { array[i] = random.Next(); } Shuffle(array); return array; } /// <summary> /// 打乱数组。 /// </summary> /// <param name="a">需要打乱的数组。</param> static void Shuffle(int[] a) { int N = a.Length; Random random = new Random(); for (int i = 0; i < N; i++) { int r = i + random.Next(N - i);// 等于StdRandom.uniform(N-i) int temp = a[i]; a[i] = a[r]; a[r] = temp; } } } }
2.1.37
解答
主要说一下第二个的实现，把一个数组循环左移/右移几位即可。
代码
using System; using System.Collections.Generic; using Sort; namespace _2._1._37 { /* * 2.1.37 * * 部分有序。 * 编写一个测试用例，生成部分有序数组，包括： * 95% 有序，其余部分为随机值。 * 所有元素和它们的正确位置的距离都不超过 10。 * 5% 的元素随机分布在整个数组中，剩下的数据都是有序的。 * 评估并验证这些输入数据对本节讨论的算法的性能的影响。 * */ class Program { // 选择排序的性能只与数组大小有关，以上三种情况耗时都是近似的。 // 插入排序的性能与逆序对数量有关，部分有序的情况下耗时会小于完全随机。 // 希尔排序与插入排序类似。 static void Main(string[] args) { InsertionSort insertionSort = new InsertionSort(); SelectionSort selectionSort = new SelectionSort(); ShellSort shellSort = new ShellSort(); int n = 10000; int[] selectionArray = new int[n]; int[] insertionArray = new int[n]; int[] 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% 有序，其余部分为随机值。 selectionArray = Sorted95Random5(n); selectionArray.CopyTo(insertionArray, 0); selectionArray.CopyTo(shellArray, 0); Console.WriteLine("95% sorted + 5% random"); Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, selectionArray)); Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, insertionArray)); Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, shellArray)); // 所有元素和它们的正确位置的距离都不超过 10。 selectionArray = RandomIn10(n); selectionArray.CopyTo(insertionArray, 0); selectionArray.CopyTo(shellArray, 0); Console.WriteLine("a sorted array that left shift 6 times"); Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, selectionArray)); Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, insertionArray)); Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, shellArray)); // 5% 的元素随机分布在整个数组中，剩下的数据都是有序的。 selectionArray = RandomIn10(n); selectionArray.CopyTo(insertionArray, 0); selectionArray.CopyTo(shellArray, 0); Console.WriteLine("95% elements is sorted while 5% elements are placed randomly"); Console.WriteLine("Selection Sort:" + SortCompare.Time(selectionSort, selectionArray)); Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, insertionArray)); Console.WriteLine("Shell Sort:" + SortCompare.Time(shellSort, shellArray)); } /// <summary> /// 生成 95% 有序，最后 5% 随机的 <see cref="int"/> 数组。 /// </summary> /// <param name="n">数组的大小。</param> /// <returns>95% 有序，最后 5% 随机的 <see cref="int"/> 数组。</returns> static int[] Sorted95Random5(int n) { int[] array = new int[n]; int randomStart = (int)(n * 0.05); Random random = new Random(); for (int i = 0; i < n - randomStart; i++) { array[i] = i; } for (int i = n - randomStart; i < n; i++) { array[i] = random.Next(); } return array; } /// <summary> /// 返回一个 <see cref="int"/> 数组，其中的每个元素和它的正确位置的距离都不超过 10。 /// </summary> /// <param name="n">数组大小。</param> /// <returns>一个 <see cref="int"/> 数组，其中的每个元素和它的正确位置的距离都不超过 10。</returns> static int[] RandomIn10(int n) { Queue<int> array = new Queue<int>(); Random random = new Random(); for (int i = 0; i < n; i++) { array.Enqueue(i); } for (int i = 0; i < 6; i++) { array.Enqueue(array.Dequeue()); } return array.ToArray(); } /// <summary> /// 生成 5% 元素随机分布，剩余有序的 <see cref="int"/> 数组。 /// </summary> /// <param name="n">需要生成的数组大小。</param> /// <returns>5% 元素随机分布，剩余有序的 <see cref="int"/> 数组。</returns> static int[] Shuffle5Percent(int n) { Random random = new Random(); int percent5 = (int)(n * 0.05); int[] randomIndex = new int[percent5]; for (int i = 0; i < percent5; i++) { randomIndex[i] = random.Next(percent5); } int[] randomValue = new int[percent5]; for (int i = 0; i < percent5; i++) { randomValue[i] = randomIndex[i]; } Shuffle(randomValue); int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = i; } for (int i = 0; i < percent5; i++) { array[randomIndex[i]] = randomValue[i]; } return array; } /// <summary> /// 打乱数组。 /// </summary> /// <param name="a">需要打乱的数组。</param> static void Shuffle(int[] a) { int N = a.Length; Random random = new Random(); for (int i = 0; i < N; i++) { int r = i + random.Next(N - i);// 等于StdRandom.uniform(N-i) int temp = a[i]; a[i] = a[r]; a[r] = temp; } } } }
2.1.38
解答
这里实现了一个 Pair 类，用来排序。
每一个元素都有相应的 key 值和 value 值，排序时只使用 key 值进行排序。
代码
using System; using Sort; namespace _2._1._38 { /* * 2.1.38 * * 不同类型的元素。 * 编写一个测试用例，生成由多种数据类型元素组成的数组，元素的主键值随机，包括： * 每个元素的主键均为 String 类型（至少长 10 个字符），并含有一个 double 值。 * 每个元素的主键均为 double 类型，并含有 10 个 String 值（每个都至少长 10 个字符）。 * 每个元素的主键均为 int 类型，并含有一个 int[20] 值。 * 评估并验证这些输入数据对本节讨论的算法的性能的影响。 * */ class Program { static void Main(string[] args) { int n = 10000; double[] 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.WriteLine("Shell Sort:" + results[2]); } /// <summary> /// 第一个测试，测试结果按照 Insertion, Selection, Shell 排序。 /// </summary> /// <param name="n">测试的数组长度。</param> /// <returns>测试结果。</returns> static double[] TestA(int n) { InsertionSort insertionSort = new InsertionSort(); SelectionSort selectionSort = new SelectionSort(); ShellSort shellSort = new ShellSort(); Random random = new Random(); // 每个元素的主键均为 String 类型（至少长 10 个字符），并含有一个 double 值。 Pair<string, double>[] array = new Pair<string, double>[n]; Pair<string, double>[] arrayBak = new Pair<string, double>[n]; for (int i = 0; i < n; i++) { array[i] = new Pair<string, double>(RandomString(20, random), random.NextDouble()); } array.CopyTo(arrayBak, 0); double[] results = new double[3]; results[0] = SortCompare.Time(insertionSort, array); arrayBak.CopyTo(array, 0); results[1] = SortCompare.Time(selectionSort, array); arrayBak.CopyTo(array, 0); results[2] = SortCompare.Time(shellSort, array); return results; } /// <summary> /// 第二个测试，测试结果按照 Insertion, Selection, Shell 排序。 /// </summary> /// <param name="n">测试的数组长度。</param> /// <returns>测试结果。</returns> static double[] TestB(int n) { InsertionSort insertionSort = new InsertionSort(); SelectionSort selectionSort = new SelectionSort(); ShellSort shellSort = new ShellSort(); Random random = new Random(); // 每个元素的主键均为 double 类型，并含有 10 个 String 值（每个都至少长 10 个字符）。 Pair<double, string[]>[] array = new Pair<double, string[]>[n]; Pair<double, string[]>[] arrayBak = new Pair<double, string[]>[n]; for (int i = 0; i < n; i++) { string[] temp = new string[10]; for (int j = 0; j < 10; j++) { temp[j] = RandomString(12, random); } array[i] = new Pair<double, string[]>(random.NextDouble(), temp); } array.CopyTo(arrayBak, 0); double[] results = new double[3]; results[0] = SortCompare.Time(insertionSort, array); arrayBak.CopyTo(array, 0); results[1] = SortCompare.Time(selectionSort, array); arrayBak.CopyTo(array, 0); results[2] = SortCompare.Time(shellSort, array); return results; } /// <summary> /// 第三个测试，测试结果按照 Insertion, Selection, Shell 排序。 /// </summary> /// <param name="n">测试的数组长度。</param> /// <returns>测试结果。</returns> static double[] TestC(int n) { InsertionSort insertionSort = new InsertionSort(); SelectionSort selectionSort = new SelectionSort(); ShellSort shellSort = new ShellSort(); Random random = new Random(); // 每个元素的主键均为 int 类型，并含有一个 int[20] 值。 Pair<int, int[]>[] array = new Pair<int, int[]>[n]; Pair<int, int[]>[] arrayBak = new Pair<int, int[]>[n]; for (int i = 0; i < n; i++) { int[] temp = new int[20]; for (int j = 0; j < 20; j++) { temp[j] = random.Next(); } array[i] = new Pair<int, int[]>(random.Next(), temp); } array.CopyTo(arrayBak, 0); double[] results = new double[3]; results[0] = SortCompare.Time(insertionSort, array); arrayBak.CopyTo(array, 0); results[1] = SortCompare.Time(selectionSort, array); arrayBak.CopyTo(array, 0); results[2] = SortCompare.Time(shellSort, array); return results; } /// <summary> /// 获取一个随机 <see cref="string"/>。 /// </summary> /// <param name="n"><see cref="string"/> 的长度。</param> /// <param name="random">随机数生成器。</param> /// <returns>获取一个随机 <see cref="string"/>。</returns> static string RandomString(int n, Random random) { char[] value = new char[n]; for (int i = 0; i < n; i++) { value[i] = (char)random.Next(char.MinValue + 10, char.MaxValue - 10); } return new string(value); } } }
a = ReadAllInts(TestCase.Properties.Resources._1Mints); linkedTime = TimeTrialLinkedStack(a); arrayTime = TimeTrialDoublingStack(a); Console.WriteLine($"1000000 {linkedTime} {arrayTime} {linkedTime / arrayTime}"); } } }
1.4.44
解答
每生成一个随机数都和之前生成过的随机数相比较。
代码
using System; namespace _1._4._44 { /* * 1.4.44 * * 生日问题。 * 编写一个程序， * 从命令行接受一个整数 N 作为参数并使用 StdRandom.uniform() 生成一系列 0 到 N-1 之间的随机整数。 * 通过实验验证产生第一个重复的随机数之前生成的整数数量为 ~√(πN/2)。 * */ class Program { static void Main(string[] args) { Random random = new Random(); int N = 10000; int[] a = new int[N]; int dupNum = 0; int times = 0; for (times = 0; times < 500; ++times) { for (int i = 0; i < N; ++i) { a[i] = random.Next(N); if (IsDuplicated(a, i)) { dupNum += i; Console.WriteLine($"生成{i + 1}个数字后发生重复"); break; } } } Console.WriteLine($"√(πN/2)={Math.Sqrt(Math.PI * N / 2.0)}，平均生成{dupNum / times}个数字后出现重复"); } /// <summary> /// 检查是否有重复的数字出现。 /// </summary> /// <param name="a">需要检查的数组。</param> /// <param name="i">当前加入数组元素的下标。</param> /// <returns>有重复则返回 true，否则返回 false。</returns> static bool IsDuplicated(int[] a, int i) { for (int j = 0; j < i; ++j) { if (a[j] == a[i]) { return true; } } return false; } } }
1.4.45
解答
建立一个布尔数组，将每次随机出来的数作为下标，将相应位置的布尔值改为 true，每次随机都检查一遍这个数组是否都是 true。
代码
using System; namespace _1._4._45 { /* * 1.4.45 * * 优惠券收集问题。 * 用和上一题相同的方式生成随机整数。 * 通过实验验证生成所有可能的整数值所需生成的随机数总量为 ~NHN。 * （这里的 HN 中 N 是下标） * */ class Program { // HN 指的是调和级数 static void Main(string[] args) { Random random = new Random(); int N = 10000; bool[] a = new bool[N]; int randomSize = 0; int times = 0; for (times = 0; times < 20; ++times) { for (int i = 0; i < N; ++i) { a[i] = false; } for(int i = 0; true; ++i) { int now = random.Next(N); a[now] = true; if (IsAllGenerated(a)) { randomSize += i; Console.WriteLine($"生成{i}次后所有可能均出现过了"); break; } } } Console.WriteLine($" NHN={N * HarmonicSum(N)}，平均生成{randomSize / times}个数字后所有可能都出现"); } /// <summary> /// 计算 N 阶调和级数的和。 /// </summary> /// <param name="N">调和级数的 N 值</param> /// <returns>N 阶调和级数的和。</returns> static double HarmonicSum(int N) { double sum = 0; for (int i = 1; i <= N; ++i) { sum += 1.0 / i; } return sum; } /// <summary> /// 检查所有数字是否都生成过了。 /// </summary> /// <param name="a">布尔数组。</param> /// <returns>全都生成则返回 true，否则返回 false。</returns> static bool IsAllGenerated(bool[] a) { foreach (bool i in a) { if (!i) return false; } return true; } } }
this.queue[index] = this.queue[this.count - 1]; this.queue[this.count - 1] = temp; this.count--; if (this.count < this.queue.Length / 4) { Resize(this.queue.Length / 2); } return temp; } /// <summary> /// 随机返回一个队列中的元素。 /// </summary> /// <returns></returns> public Item Sample() { if (IsEmpty()) { throw new InvalidOperationException(); } Random random = new Random(); int index = random.Next(this.count); return this.queue[index]; } } }
1.3.36
解答
实现方法和 1.3.34 类似，初始化迭代器的时候同时初始化一个随机访问序列。
代码
RandomQueue.cs
using System; using System.Collections; using System.Collections.Generic; namespace _1._3._36 { public class RandomQueue<Item> : IEnumerable<Item> { private Item[] queue; private int count; /// <summary> /// 新建一个随机队列。 /// </summary> public RandomQueue() { this.queue = new Item[2]; this.count = 0; } /// <summary> /// 判断队列是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return this.count == 0; } /// <summary> /// 为队列重新分配内存空间。 /// </summary> /// <param name="capacity"></param> private void Resize(int capacity) { if (capacity <= 0) { throw new ArgumentException(); } Item[] temp = new Item[capacity]; for (int i = 0; i < this.count; ++i) { temp[i] = this.queue[i]; } this.queue = temp; } /// <summary> /// 向队列中添加一个元素。 /// </summary> /// <param name="item">要向队列中添加的元素。</param> public void Enqueue(Item item) { if (this.queue.Length == this.count) { Resize(this.count * 2); } this.queue[this.count] = item; this.count++; } /// <summary> /// 从队列中随机删除并返回一个元素。 /// </summary> /// <returns></returns> public Item Dequeue() { if (IsEmpty()) { throw new InvalidOperationException(); } Random random = new Random(DateTime.Now.Millisecond); int index = random.Next(this.count); Item temp = this.queue[index]; this.queue[index] = this.queue[this.count - 1]; this.queue[this.count - 1] = temp; this.count--; if (this.count < this.queue.Length / 4) { Resize(this.queue.Length / 2); } return temp; } /// <summary> /// 随机返回一个队列中的元素。 /// </summary> /// <returns></returns> public Item Sample() { if (IsEmpty()) { throw new InvalidOperationException(); } Random random = new Random(); int index = random.Next(this.count); return this.queue[index]; } public IEnumerator<Item> GetEnumerator() { return new RandomQueueEnumerator(this.queue, this.count); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } private class RandomQueueEnumerator : IEnumerator<Item> { private int current; private int count; private Item[] queue; private int[] sequence; public RandomQueueEnumerator(Item[] queue, int count) { this.count = count; this.queue = queue; this.current = -1; this.sequence = new int[this.count]; for (int i = 0; i < this.count; ++i) { this.sequence[i] = i; } Shuffle(this.sequence, DateTime.Now.Millisecond); } /// <summary> /// 随机打乱数组。 /// </summary> /// <param name="a">需要打乱的数组。</param> /// <param name="seed">随机种子值。</param> private void Shuffle(int[] a, int seed) { int N = a.Length; Random random = new Random(seed); for (int i = 0; i < N; ++i) { int r = i + random.Next(N - i); int temp = a[i]; a[i] = a[r]; a[r] = temp; } } Item IEnumerator<Item>.Current => this.queue[this.sequence[this.current]]; object IEnumerator.Current => this.queue[this.sequence[this.current]]; void IDisposable.Dispose() { this.current = -1; this.sequence = null; this.queue = null; } bool IEnumerator.MoveNext() { if (this.current == this.count - 1) return false; this.current++; return true; } void IEnumerator.Reset() { this.current = -1; } } } }
1.3.37
解答
也就是约瑟夫问题，官方给出的 JAVA 版答案：Josephus.java。
报数时将一个人出队然后入队来模拟一个环。
报到 M 个后将那个人出队但不入队（删除）
随后继续循环。
代码
using System; using Generics; namespace _1._3._37 { /* * 1.3.37 * * Josephus 问题。 * 在这个古老的问题中，N 个身陷绝境的人一致同意通过以下方式减少生存人数。 * 他们围坐成一圈（位置记作 0 到 N-1）并从第一个人开始报数， * 报到 M 的人会被杀死，直到最后一个人留下来。 * 传说中 Josephus 找到了不会被杀死的位置。 * 编写一个 Queue 的用例 Josephus，从命令行接受 N 和 M 并打印出人们被杀死的顺序 * （这也将显示 Josephus 在圈中的位置）。 * */ class Program { static void Main(string[] args) { int numOfPeople = 7; int callForDeath = 2; Queue<int> queue = new Queue<int>(); for (int i = 0; i < numOfPeople; ++i) { queue.Enqueue(i); } while (!queue.IsEmpty()) { for (int i = 0; i < callForDeath - 1; ++i) { queue.Enqueue(queue.Dequeue()); } Console.Write(queue.Dequeue() + " "); } Console.WriteLine(); } } }
1.3.38
解答
这里采用“假删除”的方式，对要删除的元素不直接删除而是打上标记，这样就可以维持插入的顺序。
代码
数组实现：
using System; namespace _1._3._38 { class ArrayBasedGeneralizeQueue<Item> { private Item[] queue; private bool[] IsVisited; private int count; private int first; private int last; /// <summary> /// 建立一个队列。 /// </summary> public ArrayBasedGeneralizeQueue() { this.queue = new Item[2]; this.IsVisited = new bool[2]; this.first = 0; this.last = 0; this.count = 0; } /// <summary> /// 检查队列是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return this.count == 0; } /// <summary> /// 为队列重新分配空间。 /// </summary> /// <param name="capacity"></param> private void Resize(int capacity) { Item[] temp = new Item[capacity]; for (int i = 0; i < this.count; ++i) { temp[i] = this.queue[i]; } this.queue = temp; bool[] t = new bool[capacity]; for (int i = 0; i < this.count; ++i) { t[i] = this.IsVisited[i]; } this.IsVisited = t; } /// <summary> /// 向队列中插入一个元素。 /// </summary> /// <param name="item">要插入队列的元素。</param> public void Insert(Item item) { if (this.count == this.queue.Length) { Resize(this.queue.Length * 2); } this.queue[this.last] = item; this.IsVisited[this.last] = false; this.last++; this.count++; } /// <summary> /// 从队列中删除并返回第 k 个插入的元素。 /// </summary> /// <param name="k">要删除元素的顺序（从 1 开始）</param> /// <returns></returns> public Item Delete(int k) { if (IsEmpty()) { throw new InvalidOperationException(); } if (k > this.last || k < 0) { throw new ArgumentOutOfRangeException(); } if (IsVisited[k - 1] == true) { throw new ArgumentException("this node had been already deleted"); } Item temp = this.queue[k - 1]; this.IsVisited[k - 1] = true; this.count--; return temp; } } }
链表实现：
using System; namespace _1._3._38 { class LinkedListBasedGeneralizeQueue<Item> { private class Node<T> { public T item; public Node<T> next; public bool IsVisited; } private Node<Item> first; private Node<Item> last; private int count; /// <summary> /// 建立一个队列。 /// </summary> public LinkedListBasedGeneralizeQueue() { this.first = null; this.last = null; this.count = 0; } /// <summary> /// 检查数组是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return this.first == null; } /// <summary> /// 在队尾插入元素。 /// </summary> /// <param name="item">需要插入的元素。</param> public void Insert(Item item) { Node<Item> oldLast = this.last; this.last = new Node<Item>() { item = item, IsVisited = false, next = null }; if (oldLast == null) { this.first = this.last; } else { oldLast.next = this.last; } count++; } /// <summary> /// 删除第 k 个插入的结点 /// </summary> /// <param name="k">结点序号（从 1 开始）</param> /// <returns></returns> public Item Delete(int k) { if (k > this.count || k <= 0) { throw new ArgumentOutOfRangeException(); } k--; //找到目标结点 Node<Item> current = this.first; for (int i = 0; i < k; ++i) { current = current.next; } if (current.IsVisited == true) { throw new ArgumentException("this node had been already deleted"); } current.IsVisited = true; return current.item; } } }
1.3.39
解答
可以直接套用队列的实现方式，在满或空时抛出相应异常。
代码
using System; namespace _1._3._39 { class RingBuffer<Item> { private Item[] buffer; private int count; private int first; //读指针 private int last; //写指针 /// <summary> /// 建立一个缓冲区。 /// </summary> /// <param name="N">缓冲区的大小。</param> public RingBuffer(int N) { this.buffer = new Item[N]; this.count = 0; this.first = 0; this.last = 0; } /// <summary> /// 检查缓冲区是否已满。 /// </summary> /// <returns></returns> public bool IsFull() { return this.count == this.buffer.Length; } /// <summary> /// 检查缓冲区是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return this.count == 0; } /// <summary> /// 向缓冲区写入数据。 /// </summary> /// <param name="item">要写入的数据。</param> public void Write(Item item) { if (IsFull()) { throw new OutOfMemoryException("buffer is full"); } this.buffer[this.last] = item; this.last = (this.last + 1) % this.buffer.Length; this.count++; } /// <summary> /// 从缓冲区读取一个数据。 /// </summary> /// <returns></returns> public Item Read() { if (IsEmpty()) { throw new InvalidOperationException(); } Item temp = this.buffer[this.first]; this.first = (this.first + 1) % this.buffer.Length; this.count--; return temp; } } }
1.3.40
解答
每次插入时都先搜索一遍链表，再判定相应动作。
代码
using System; using System.Text; namespace _1._3._40 { class MoveToFront<Item> { private class Node<T> { public T item; public Node<T> next; } private Node<Item> first; private int count; /// <summary> /// 检查编码组是否为空。 /// </summary> /// <returns></returns> public bool IsEmpty() { return this.first == null; } /// <summary> /// 建立一个前移编码组。 /// </summary> public MoveToFront() { this.first = null; this.count = 0; } /// <summary> /// 找到相应元素的前驱结点。 /// </summary> /// <param name="item">要寻找的元素。</param> /// <returns></returns> private Node<Item> Find(Item item) { if (IsEmpty()) { return null; } Node<Item> current = this.first; while (current.next != null) { if (current.next.item.Equals(item)) { return current; } current = current.next; } return null; } /// <summary> /// 前移编码插入。 /// </summary> /// <param name="item">需要插入的元素。</param> public void Insert(Item item) { Node<Item> temp = Find(item); if (temp == null) { temp = new Node<Item>() { item = item, next = this.first }; this.first = temp; this.count++; } else if (temp != null && this.count != 1) { Node<Item> target = temp.next; temp.next = temp.next.next; target.next = this.first; this.first = target; } } /// <summary> /// 查看第一个元素。 /// </summary> /// <returns></returns> public Item Peek() { if (this.first == null) { throw new InvalidOperationException(); } return this.first.item; } public override string ToString() { StringBuilder s = new StringBuilder(); Node<Item> current = this.first; while (current != null) { s.Append(current.item.ToString()); s.Append(" "); current = current.next; } return s.ToString(); } } }
1.3.41
解答
可以按照书上的提示出队再入队，也可以直接用迭代器访问一遍进行复制。
代码
/// <summary> /// 复制构造函数。 /// </summary> /// <param name="r"></param> public Queue(Queue<Item> r) { foreach (Item i in r) { Enqueue(i); } }
1.3.42
解答
直接把链栈的整个链表复制一份即可。
代码
/// <summary> /// 复制构造函数。 /// </summary> /// <param name="s"></param> public Stack(Stack<Item> s) { if (s.first != null) { this.first = new Node<Item>(s.first); for (Node<Item> x = this.first; x.next != null; x = x.next) { x.next = new Node<Item>(x.next); } } this.count = s.count; }
1.3.43
解答
C# 中可以用 Directory 类里面的几个方法来获得文件路径和文件名。
代码
using System; using System.IO; using System.Linq; namespace _1._3._43 { /* * 1.3.43 * * 文件列表。 * 文件夹就是一列文件和文件夹的列表。 * 编写一个程序，从命令行接受一个文件夹名作为参数， * 打印出该文件夹下的所有文件并用递归的方式在所有子文件夹的名下（缩进）列出其下的所有文件。 * */ class Program { static void Main(string[] args) { //获取当前目录 string path = Directory.GetCurrentDirectory(); path = Directory.GetParent(path).FullName; path = Directory.GetParent(path).FullName; //获取文件 Console.WriteLine(path + "中的所有文件"); Search(path, 0); } static void Search(string path, int tabs) { string[] dirs = Directory.GetDirectories(path); string[] files = Directory.GetFiles(path); foreach (string p in dirs) { for (int i = 0; i < tabs; ++i) { Console.Write(" "); } Console.WriteLine(p.Split('\').Last()); Search(p, tabs + 1); } foreach (string f in files) { for (int i = 0; i < tabs; ++i) { Console.Write(" "); } Console.WriteLine(f.Split('\').Last()); } } } }
1.3.44
解答
这里我们使用两个栈来模拟缓冲区。
向左/向右移动 = 从左/右栈弹出相应数量的元素并压入另外一个栈。
插入/删除 = 左栈压入/弹出一个元素。
字符数量 = 左栈数量 + 右栈数量。
代码
using Generics; namespace _1._3._44 { class Buffer { private Stack<char> leftside; private Stack<char> rightside; /// <summary> /// 建立一个文本缓冲区。 /// </summary> public Buffer() { this.leftside = new Stack<char>(); this.rightside = new Stack<char>(); } /// <summary> /// 在光标位置插入字符 c。 /// </summary> /// <param name="c">要插入的字符。</param> public void Insert(char c) { this.leftside.Push(c); } /// <summary> /// 删除并返回光标位置的字符。 /// </summary> /// <returns></returns> public char Delete() { return this.leftside.Pop(); } /// <summary> /// 将光标向左移动 k 个位置。 /// </summary> /// <param name="k">光标移动的距离。</param> public void Left(int k) { for (int i = 0; i < k; ++i) { this.rightside.Push(this.leftside.Pop()); } } /// <summary> /// 将光标向右移动 k 个位置。 /// </summary> /// <param name="k">光标移动的距离。</param> public void Right(int k) { for (int i = 0; i < k; ++i) { this.leftside.Push(this.rightside.Pop()); } } /// <summary> /// 返回缓冲区中的字符数量。 /// </summary> /// <returns></returns> public int Size() { return this.leftside.Size() + this.rightside.Size(); } /// <summary> /// 将缓冲区的内容输出，这将使光标重置到最左端。 /// </summary> /// <returns></returns> public string Getstring() { while (!leftside.IsEmpty()) { this.rightside.Push(this.leftside.Pop()); } return rightside.ToString(); } } }
1.3.45
解答
书上已经给出了思路，简单说明一下。
第一问是给定输入判断是否会下溢出，只要记录栈中元素的数量即可，一旦为负数则返回 true。
第二问是给定输出判断是否可能。
对于输出序列中的每一个数，如果栈顶为空或者栈顶数字小于当前输出序列的数，那么就从输入序列中输入数字，直到栈顶数字和当前输出序列中的数字相等。
如果当前输出序列中的数字和栈顶元素相等，从栈中弹出相应元素。
最后如果栈为空则可能，否则不可能。
可以结合习题 1.3.3 的解答查看。
通用解法见下一题。
代码
using System; using Generics; namespace _1._3._45 { /* * 1.3.45 * * 栈的可生成性。 * 假设我们的栈测试用例会进行一系列的入栈和出栈操作， * 序列中的整数 0, 1, ... , N - 1 （按此先后顺序排列）表示入栈操作，N个减号表示出栈操作。 * 设计一个算法，判定给定的混合序列是否会使数组向下溢出 * （你使用的空间量与 N 无关，即不能用某种数据结构存储所有整数）。 * 设计一个线性时间算法判定我们的测试用例能否产生某个给定的排列 * （这取决于出栈操作指令的出现位置）。 * */ class Program { static void Main(string[] args) { //给定输入序列，判断是否会出现下溢出。 string input = "- 0 1 2 3 4 5 6 7 8 9 - - - - - - - - -"; Console.WriteLine(IsUnderflow(input.Split(' ')));//True input = "0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 -"; Console.WriteLine(IsUnderflow(input.Split(' ')));//False //给定输出序列，判定是否可能。 int[] output = { 4, 3, 2, 1, 0, 9, 8, 7, 6, 5 }; Console.WriteLine(IsOutputPossible(output));//True output = new int[]{ 4, 6, 8, 7, 5, 3, 2, 9, 0, 1}; Console.WriteLine(IsOutputPossible(output));//False } /// <summary> /// 判断是否会出现下溢出。 /// </summary> /// <param name="input">输入序列。</param> /// <returns></returns> static bool IsUnderflow(string[] input) { //记录栈中元素数量，如果元素数量小于 0 则会出现下溢出。 int count = 0; foreach (string s in input) { if (count < 0) { return true; } if (s.Equals("-")) { count--; } else { count++; } } return false; } /// <summary> /// 判断输出序列是否正确。 /// </summary> /// <param name="output">输出序列。</param> /// <returns></returns> static bool IsOutputPossible(int[] output) { int input = 0; int N = output.Length; Stack<int> stack = new Stack<int>(); foreach (int i in output) { //如果栈为空，则从输入序列中压入一个数。 if (stack.IsEmpty()) { stack.Push(input); input++; } //如果输入序列中的所有数都已经入栈过了，跳出循环。 if (input == N && stack.Peek() != i) { break; } //如果输出序列的下一个数不等于栈顶的数，那么就从输入序列中压入一个数。 while (stack.Peek() != i && input < N) { stack.Push(input); input++; } //如果栈顶的数等于输出的数，弹出它。 if (stack.Peek() == i) { stack.Pop(); } } return stack.IsEmpty(); } } }
1.3.46
解答
这道题的解答参考了这篇博文：http://ceeji.net/blog/forbidden-triple-for-stack-generability/。
显然书中的解答已经十分明确，这里简单说明一下：
首先有结论：对于栈顶元素 Sn，栈中所有小于 Sn 的值都以递减形式保存（已经输出的不算）。
表现在输出序列中，Sn 输出之后，如果有小于 Sn 的值输出，其顺序必定是递减的。
例如序列 4 3 2 1 0 9 8 7 6 5
4 输出之后，3 2 1 0 递减输出；9 输出之后，8 7 6 5 递减输出。
依次验证其中的每个值都能满足结论。
而对于序列 4 6 8 7 5 3 2 9 0 1
对于 4，之后的 3 2 1 0 并不是以递减顺序输出的，因此这个序列是不合法的。
1.3.47
解答
这里用的都是链式结构，头尾相接即可。
代码
Queue：
/// <summary> /// 在当前队列之后附加一个队列。 /// </summary> /// <param name="q1">需要被附加的队列。</param> /// <param name="q2">需要附加的队列（将被删除）。</param> public static Queue<Item> Catenation(Queue<Item> q1, Queue<Item> q2) { if (q1.IsEmpty()) { q1.first = q2.first; q1.last = q2.last; q1.count = q2.count; } else { q1.last.next = q2.first; q1.last = q2.last; q1.count += q2.count; } q2 = null; return q1; }
Stack：
/// <summary> /// 将两个栈连接。 /// </summary> /// <param name="s1">第一个栈。</param> /// <param name="s2">第二个栈（将被删除）。</param> /// <returns></returns> public static Stack<Item> Catenation(Stack<Item> s1, Stack<Item> s2) { if (s1.IsEmpty()) { s1.first = s2.first; s1.count = s2.count; } else { Node<Item> last = s1.first; while (last.next != null) { last = last.next; } last.next = s2.first; s1.count += s2.count; } s2 = null; return s1; }
Steque：
/// <summary> /// 将两个 Steque 连接。 /// </summary> /// <param name="s1">第一个 Steque </param> /// <param name="s2">第二个 Steque （将被删除）</param> /// <returns></returns> public static Steque<Item> Catenation(Steque<Item> s1, Steque<Item> s2) { if (s1.IsEmpty()) { s1.first = s2.first; s1.last = s2.last; s1.count = s2.count; } else { s1.last.next = s2.first; s1.count += s2.count; } s2 = null; return s1; }
1.3.48
解答
按照双向队列原本的操作就可以实现，需要维护两个栈的长度以防越界。（左侧栈弹出了右侧栈栈底的内容）
代码
using System; using System.Collections; using System.Collections.Generic; namespace _1._3._48 { public class DeStack<Item> : IEnumerable<Item> { private class DoubleNode<T> { public T item; public DoubleNode<T> next; public DoubleNode<T> prev; } DoubleNode<Item> first; DoubleNode<Item> last; int leftcount; int rightcount; /// <summary> /// 默认构造函数，建立一个双端栈。 /// </summary> public DeStack() { this.first = null; this.last = null; this.leftcount = 0; this.rightcount = 0; } /// <summary> /// 检查左侧栈是否为空。 /// </summary> /// <returns></returns> public bool IsLeftEmpty() { return this.leftcount == 0; } /// <summary> /// 检查右侧栈是否为空。 /// </summary> /// <returns></returns> public bool IsRightEmpty() { return this.rightcount == 0; } /// <summary> /// 返回左侧栈中元素的数量。 /// </summary> /// <returns></returns> public int LeftSize() { return this.leftcount; } /// <summary> /// 返回右侧栈中元素的数量。 /// </summary> /// <returns></returns> public int RightSize() { return this.rightcount; } /// <summary> /// 向左端添加一个元素。 /// </summary> /// <param name="item">要添加的元素。</param> public void PushLeft(Item item) { DoubleNode<Item> oldFirst = this.first; this.first = new DoubleNode<Item>() { item = item, prev = null, next = oldFirst }; if (oldFirst == null) { this.last = this.first; } else { oldFirst.prev = this.first; } this.leftcount++; } /// <summary> /// 向右端添加一个元素。 /// </summary> /// <param name="item">要添加的元素。</param> public void PushRight(Item item) { DoubleNode<Item> oldLast = this.last; this.last = new DoubleNode<Item>() { item = item, prev = oldLast, next = null }; if (oldLast == null) { this.first = this.last; } else { oldLast.next = this.last; } this.rightcount++; } /// <summary> /// 从右端删除并返回一个元素。 /// </summary> /// <returns></returns> public Item PopRight() { if (IsRightEmpty()) { throw new InvalidOperationException(); } Item temp = this.last.item; this.last = this.last.prev; this.rightcount--; if (this.last == null) { this.first = null; } else { this.last.next.item = default(Item); this.last.next = null; } return temp; } /// <summary> /// 从左端删除并返回一个元素。 /// </summary> /// <returns></returns> public Item PopLeft() { if (IsLeftEmpty()) { throw new InvalidOperationException(); } Item temp = this.first.item; this.first = this.first.next; this.leftcount--; if (this.first == null) { this.last = null; } else { this.first.prev.item = default(Item); this.first.prev = null; } return temp; } public IEnumerator<Item> GetEnumerator() { return new DequeEnumerator(this.first); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } private class DequeEnumerator : IEnumerator<Item> { private DoubleNode<Item> current; private DoubleNode<Item> first; public DequeEnumerator(DoubleNode<Item> first) { this.current = new DoubleNode<Item>(); this.current.next = first; this.current.prev = null; this.first = this.current; } public Item Current => current.item; object IEnumerator.Current => current.item; public void Dispose() { this.current = null; this.first = null; } public bool MoveNext() { if (this.current.next == null) return false; this.current = this.current.next; return true; } public void Reset() { this.current = this.first; } } } }
1.3.49
解答
用六个栈即可实现，具体请查看我的这篇博文（有点复杂）：用 6 个栈实现一个 O(1) 队列。
1.3.50
解答
初始化迭代器的时候记录栈已经进行过的 Pop 和 Push 数，迭代的时候检查这两个值是否改变，一旦改变就抛出异常。
代码
修改后的迭代器代码：
private class StackEnumerator : IEnumerator<Item> { private Stack<Item> s; private int popcount; private int pushcount; private Node<Item> current; public StackEnumerator(Stack<Item> s) { this.s = s; this.current = s.first; this.popcount = s.popcount; this.pushcount = s.pushcount; } Item IEnumerator<Item>.Current => current.item; object IEnumerator.Current => current.item; void IDisposable.Dispose() { this.current = null; this.s = null; } bool IEnumerator.MoveNext() { if (s.popcount != this.popcount || s.pushcount != this.pushcount) throw new InvalidOperationException("Stack has been modified"); if (this.current.next == null) return false; this.current = this.current.next; return true; } void IEnumerator.Reset() { this.current = this.s.first; } }
: #0000ff;">return this.rightcount; } /// <summary> /// 向左端添加一个元素。 /// </summary> /// <param name="item">要添加的元素。</param> public void PushLeft(Item item) { DoubleNode<Item> oldFirst = this.first; this.first = new DoubleNode<Item>() { item = item, prev = null, next = oldFirst }; if (oldFirst == null) { this.last = this.first; } else { oldFirst.prev = this.first; } this.leftcount++; } /// <summary> /// 向右端添加一个元素。 /// </summary> /// <param name="item">要添加的元素。</param> public void PushRight(Item item) { DoubleNode<Item> oldLast = this.last; this.last = new DoubleNode<Item>() { item = item, prev = oldLast, next = null }; if (oldLast == null) { this.first = this.last; } else { oldLast.next = this.last; } this.rightcount++; } /// <summary> /// 从右端删除并返回一个元素。 /// </summary> /// <returns></returns> public Item PopRight() { if (IsRightEmpty()) { throw new InvalidOperationException(); } Item temp = this.last.item; this.last = this.last.prev; this.rightcount--; if (this.last == null) { this.first = null; } else { this.last.next.item = default(Item); this.last.next = null; } return temp; } /// <summary> /// 从左端删除并返回一个元素。 /// </summary> /// <returns></returns> public Item PopLeft() { if (IsLeftEmpty()) { throw new InvalidOperationException(); } Item temp = this.first.item; this.first = this.first.next; this.leftcount--; if (this.first == null) { this.last = null; } else { this.first.prev.item = default(Item); this.first.prev = null; } return temp; } public IEnumerator<Item> GetEnumerator() { return new DequeEnumerator(this.first); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } private class DequeEnumerator : IEnumerator<Item> { private DoubleNode<Item> current; private DoubleNode<Item> first; public DequeEnumerator(DoubleNode<Item> first) { this.current = new DoubleNode<Item>(); this.current.next = first; this.current.prev = null; this.first = this.current; } public Item Current => current.item; object IEnumerator.Current => current.item; public void Dispose() { this.current = null; this.first = null; } public bool MoveNext() { if (this.current.next == null) return false; this.current = this.current.next; return true; } public void Reset() { this.current = this.first; } } } }
1.3.49
题目
栈与队列。
用有限个栈实现一个队列，
保证每个队列操作（在最坏情况下）都只需要常数次的栈操作。
解答
用六个栈即可实现，具体请查看我的这篇博文（有点复杂）：用 6 个栈实现一个 O(1) 队列。
1.3.50
题目
快速出错的迭代器。
修改 Stack 的迭代器代码，确保一旦用例在迭代器中（通过 push() 或 pop() 操作）修改集合数据就抛出一个 java.util.ConcurrentModificationException 异常。
解答
初始化迭代器的时候记录栈已经进行过的 Pop 和 Push 数，迭代的时候检查这两个值是否改变，一旦改变就抛出异常。
代码
修改后的迭代器代码：
private class StackEnumerator : IEnumerator<Item> { private Stack<Item> s; private int popcount; private int pushcount; private Node<Item> current; public StackEnumerator(Stack<Item> s) { this.s = s; this.current = s.first; this.popcount = s.popcount; this.pushcount = s.pushcount; } Item IEnumerator<Item>.Current => current.item; object IEnumerator.Current => current.item; void IDisposable.Dispose() { this.current = null; this.s = null; } bool IEnumerator.MoveNext() { if (s.popcount != this.popcount || s.pushcount != this.pushcount) throw new InvalidOperationException("Stack has been modified"); if (this.current.next == null) return false; this.current = this.current.next; return true; } void IEnumerator.Reset() { this.current = this.s.first; } }