求一个能够用java识别扑克牌花色的源代码，重谢····
[问题点数：100分]
求一个能够用java识别扑克牌花色的源代码，重谢····
[问题点数：100分]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2016年7月 扩充话题大版内专家分月排行榜第二
2017年1月 Java大版内专家分月排行榜第三2016年12月 扩充话题大版内专家分月排行榜第三2016年10月 扩充话题大版内专家分月排行榜第三2016年6月 扩充话题大版内专家分月排行榜第三
匿名用户不能发表回复！|豆丁微信公众号
君，已阅读到文档的结尾了呢~~
精品：扑克牌四种花色 扑克牌花色 扑克牌花色大小 扑克牌四花色 扑克牌有几种花色 扑克牌四个花色代表 扑克牌花色顺序 扑克牌的花色 扑克牌花色英语 一副扑克有四种花色
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
Pack_2C#4.0实现扑克牌中的四种花色
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口C#程序设计大作业题目及要求(15-16-1)-学路网-学习路上 有我相伴
C#程序设计大作业题目及要求(15-16-1)
来源：互联网
贡献&责任编辑：鲁倩 &
系主任签名
2015 ――2016
卷课程编号：
课程名称：
C#程序设计
试卷类型：A
考试形式：开
卷 考试时间：
分钟题号一二三四五六七八总分总分人得分得分评分人、一、\t大作业设计完成时间：2015年第16周结束后收齐上交二、\t大作业设计内容共四大题：第一题：C#程序设计题，编写一个扑克牌游戏，用计算机模拟洗牌，分发给四个玩家并将四个玩家的牌显示输出，并进一步设计，玩家的牌按照排序算法从大到小依次排序，并显示输出。
提示：用一维数组Card存放52张牌（不考虑大小王），用二维数组Player存放四个玩家的牌，用三位整数表示牌的种类，后两位表示牌号。例如：101，102，103……,113分别表示红桃A，红桃2,……红桃K说明：1．要求首先通过设计一个C#程序，实现上述题目的要求。2．给出源程序代码实现程序要求功能，能够编译生成可执行文件。第二题：窗体应用程序设计题，在.NET平台下以C#为源语言，新建一个计算器窗体CalForm 在其中添加各种控件，要求通过输入数据能进行简单的加，减，乘，除，开方，指数,倒数等四则运算，并能进一步完成三角函数的运算；请自己设计窗体应用程序编码实现所需功能。说明：1．要求首先通过向导生成一个计算器窗体的应用程序框架。2．通过在窗体上添加控件，设置其属性并且调整好各控件的位置。3．在应用程序设计过程中为控件添加事件处理程序，实现计算器功能。4．完整实现程序要求的功能，能够编译生成可执行文件。第三题：窗体程序设计题，要求创建一个窗体应用程序，以实现对社区居民的经常采用的体育锻炼方式的调查（主要有篮球，游泳，跑步，广场舞，散步等）。要求：通过单击主窗体上的调查按钮，弹出一个调查对话框，然后在该对话框中选择相应的选项，并且统计每个体育爱好的具体居民人数反馈给用户。说明：1．要求通过设计主窗体和对话框的基本框架，编码以实现两者之间的数据交互完成所需功能。2．实现程序功能要求，能够按程序要求编译生成可执行文件。第四题：综合设计题编写一个窗体应用程序将某个班级学生的成绩保存在一个文件中，此文件必须保存每个学生的学号，姓名，课程及考试成绩，并且用户可以按要求读取该文件在一个只读的窗体控件中显示其中内容。说明：1. 实现程序功能要求，能够按程序要求编译生成可执行文件。三、大作业的格式标准1. 每个同学的作品是用Vs.NET2005开发环境制作完成。2. 每个同学的作品存放在一个单独的文件夹中，其中存放四个完成的题目，该文件夹的名称就是该学生的班级，姓名，及学号。3. 每个学生的作品必须按照老师规定的方式，在规定时间内统一刻录成光盘上交，可以采用一个班级一起刻录成一张光盘上交。四、评分标准：（四题都必须完成，共100分）以百分制记。第一题 25分1.游戏程序设计基本框架结构完整，源程序基本合理，能显示基本要求15分（要求程序基本清楚，程序结构准确。）2.程序设计功能准确完成，代码优化合理，功能完善准确占10分（其中包含题目要求的各项功能，成功编译执行等设计规范并作为评分依据。）第二题 25分1. 窗体程序设计基本框架结构完整，源程序基本合理，能显示基本要求15分（要求程序基本清楚，程序结构准确。）2. 窗体程序设计功能准确完成，并能按进一步完善计算器的各种功能要求10分（其中包含题目要求的各项功能，成功编译执行等设计规范并作为评分依据。）第三题 25分 1. 窗体程序设计基本框架结构完整，源程序基本合理，能正确使用控件设置15分（要求程序基本清楚，程序结构准确。）2. 窗体程序设计功能准确完成，能按要求准确反馈调查结果，优化完成各项功能占10分（其中包含题目要求的各项功能，成功编译执行等设计规范并作为评分依据。）第四题 25分 1. 文件窗体程序设计基本框架结构完整，源程序基本合理 15分（要求程序基本清楚，程序结构准确。）2. 文件程序设计功能准确完成，能按要求准确优化完成各项功能占10分（其中包含题目要求的各项功能，成功编译执行等设计规范并作为评分依据。）以下内容为系统自动转化的文字版，可能排版等有问题，仅供您参考：学院 制卷份数出卷教师 专 业罗坤系主任签名 班级编号江汉大学2015 ――2016学年第1 学期考课程编号： 试卷类型：A 题号 得分 一
、B 二 卷 三试试、闭 六卷C#程序设计 卷 考试时间： 七 八 总分 分钟 总分人课程名称： 考试形式：开 四 五得分评分人、一、大作业设计完成时间：2015 年第 16 周结束后收齐上交二、大作业设计内容共四大题：第一题：C#程序设计题，编写一个扑克牌游戏，用计算机模拟洗牌，分发给四个玩家并将四个 玩家的牌显示输出，并进一步设计，玩家的牌按照排序算法从大到小依次排序，并显示输 出。 提示：用一维数组 Card 存放 52 张牌（不考虑大小王） ，用二维数组 Player 存放四个玩 家的牌，用三位整数表示牌的种类，后两位表示牌号。 例如：101，102，103……,113 分别表示红桃 A，红桃 2,……红桃 K 说明： 1．要求首先通过设计一个 C#程序，实现上述题目的要求。 2．给出源程序代码实现程序要求功能，能够编译生成可执行文件。第二题：窗体应用程序设计题，在.NET 平台下以 C#为源语言，新建一个计算器窗体 CalForm 在 其中添加各种控件，要求通过输入数据能进行简单的加，减，乘，除，开方，指数 ,倒数 等四则运算，并能进一步完成三角函数的运算；请自己设计窗体应用程序编码实现所需功 能。1说明： 1．要求首先通过向导生成一个计算器窗体的应用程序框架。 2．通过在窗体上添加控件，设置其属性并且调整好各控件的位置。 3．在应用程序设计过程中为控件添加事件处理程序，实现计算器功能。 4．完整实现程序要求的功能，能够编译生成可执行文件。第三题：窗体程序设计题，要求创建一个窗体应用程序，以实现对社区居民的经常采用的体育 锻炼方式的调查（主要有篮球，游泳，跑步，广场舞，散步等） 。要求：通过单击主窗体 上的调查按钮，弹出一个调查对话框，然后在该对话框中选择相应的选项，并且统计每个 体育爱好的具体居民人数反馈给用户。 说明： 1．要求通过设计主窗体和对话框的基本框架，编码以实现两者之间的数据交互完成所需功能。 2．实现程序功能要求，能够按程序要求编译生成可执行文件。第四题：综合设计题 编写一个窗体应用程序将某个班级学生的成绩保存在一个文件中，此文件必须保存每个 学生的学号，姓名，课程及考试成绩，并且用户可以按要求读取该文件在一个只读的窗体 控件中显示其中内容。 说明： 1. 实现程序功能要求，能够按程序要求编译生成可执行文件。2三、大作业的格式标准 1. 每个同学的作品是用 Vs.NET2005 开发环境制作完成。 2. 每个同学的作品存放在一个单独的文件夹中，其中存放四个完成的题目，该文件夹的名称 就是该学生的班级，姓名，及学号。 3. 每个学生的作品必须按照老师规定的方式，在规定时间内统一刻录成光盘上交，可以采 用一个班级一起刻录成一张光盘上交。 四、评分标准： （四题都必须完成，共 100 分） 以百分制记。 第一题 25 分 1.游戏程序设计基本框架结构完整，源程序基本合理，能显示基本要求 15 分（要求程序基本 清楚，程序结构准确。 ） 2.程序设计功能准确完成，代码优化合理，功能完善准确占 10 分（其中包含题目要求的各项 功能，成功编译执行等设计规范并作为评分依据。 ） 第二题 25 分 1. 窗体程序设计基本框架结构完整，源程序基本合理，能显示基本要求 15 分（要求程序基 本清楚，程序结构准确。 ） 2. 窗体程序设计功能准确完成，并能按进一步完善计算器的各种功能要求 10 分（其中包含 题目要求的各项功能，成功编译执行等设计规范并作为评分依据。 ） 第三题 25 分 1. 窗体程序设计基本框架结构完整，源程序基本合理，能正确使用控件设置 15 分（要求程 序基本清楚，程序结构准确。 ） 2. 窗体程序设计功能准确完成， 能按要求准确反馈调查结果， 优化完成各项功能占 10 分 （其 中包含题目要求的各项功能，成功编译执行等设计规范并作为评分依据。 ） 第四题 25 分 1. 文件窗体程序设计基本框架结构完整，源程序基本合理 15 分（要求程序基本清楚，程序 结构准确。 ） 2. 文件程序设计功能准确完成，能按要求准确优化完成各项功能占 10 分（其中包含题目要 求的各项功能，成功编译执行等设计规范并作为评分依据。 ）3
与《》相关：
- Copyright & 2017 www.xue63.com All Rights Reserved算法（第四版）C#题解——2.1
时间： 21:22:49
&&&& 阅读：135
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&写在前面
整个项目都托管在了 Github 上：
这一节内容可能会用到的库文件有 Sort和 SortData，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。
按照算法 2.1 所示轨迹的格式给出选择排序是如何将数组 E A S Y Q U E S T I O N 排序的。
在选择排序中，一个元素最多可能会被交换多少次？平均可能会被交换多少次？
最多会被交换 n 次，只要将一个有序数列循环右移一位就可以构造这样的情况。
平均每个元素被交换了 N/N=1 次。（总共 N 个元素，总共发生了 N 次交换）
构造一个含有 N 个元素的数组，使选择排序（算法 2.1）运行过程中 a[j] & a[min] （由此 min 会不断更新）成功的次数最大。
你需要一个逆序的数组。
例如：9 8 7 6 5 4 3 2 1
i=0 条件满足 8 次，1 和 9 交换，1 8 7 6 5 4 3 2 9。
i=1 条件满足 6 次，2 和 8 交换，1 2 7 6 5 4 3 8 9。
i=2 条件满足 4 次，3 和 7 交换，1 2 3 6 5 4 7 8 9。
i=3 条件满足 2 次，4 和 6 交换。1 2 3 4 5 6 7 8 9。
一共满足了 8+6+4+2=20 次
按照算法 2.2 所示轨迹的格式给出插入排序是如何将数组 E A S Y Q U E S T I O N 排序的。
构造一个含有 N 个元素的数组，使插入排序（算法 2.2）运行过程中内循环（for）的两个判断结果总是假。
j & <span style="color: # && less(a[j], a[j - <span style="color: #])
第一个条件属于循环计数用的条件，与数组元素无关；
第二个条件当 a[j] 和 a[j - 1] 是一组逆序对时满足，因此这个条件总是为假 = 数组没有逆序对 = 数组有序。
因此只要输入已经排好序的数组即可。
逆序对：指序列中顺序相反的两个数，例如 1 2 3 4 5 7 6 8 9 中的 7 6。
在所有主键都相同时，选择排序和插入排序谁更快？
插入排序更快。
选择排序无论如何都需要 n + (n-1) + (n-2) + …& + 1 = n^2/2 次比较。
插入排序在这种情况下只需要 n 次比较。（所有主键相同 = 数组已排序）
对于逆序数组，选择排序和插入排序谁更快？
假设比较的开销小于等于交换的开销，此时选择排序更快，具体比较见下表。
假设元素只可能有三种值，使用插入排序处理这样一个随机数组的运行时间是线性的还是平方级别的？或是介于两者之间？
平方级别。
如果数组中元素各不相同，那么这个结论很容易证明（一般的插入排序）。
接下来我们证明有重复元素的情况下，这个结论仍然成立：
首先对于插入排序过程中的某一时刻，我们有下图这样的一般情况：
其中，1，2，3 分别代表三种不同的取值以及其先后顺序。
假设这是第 i 次插入前，如果第 i 次插入的是 1，我们需要交换 b+c 次，插入 2 则需要交换 c 次，插入 3 则不需要交换。
根据题意，这是一个随机数组，我们假设其为均匀分布，那么三种取值的出现几率相等。
第 i 次插入所需要的平均交换次数即为：
第 i 次插入后，b + 2c 视插入的元素不同会出现不同的变化：
如果插入的是 1，那么 b+2c 的值不会变化。
如果插入的是 2，那么 b+2c 的值增加 1。
如果插入的是 3，那么 b+2c 的值增加 2。
同样由于三种取值的概率相等，我们得出第 i + 1 次插入平均需要交换的次数为：
也就是说，平均每次插入都会使下一次插入的交换次数增加 1/3。
令 i=0，此时交换次数为 0，i+1 的交换次数即为 1/3，i+2 的交换次数即为 2/3，以此类推。
我们可以得出总交换次数：
由此证明，在元素取值为 3 种且出现概率相等时，插入排序的交换开销时平方级别的。
比较开销和交换开销类似，一般情况下比较次数=交换次数+1，除非插入的数是已知最小的数（移动到最左侧），这个时候比较次数和交换次数相等。
因此比较次数=交换次数+N-e，e 是一个不大于 N 的数，代表插入的数是已知最小的数这种情况发生的次数。
根据上式可以得出结论：在元素取值为 3 种且出现概率相等时，插入排序的比较开销也是平方级别的。
综合两个结论即可证明插入排序的开销在题目描述的情况下是平方级别的。
证明完毕。
按照算法 2.3 所示轨迹的格式给出希尔排序是如何将数组 E A S Y S H E L L S O R T Q U E S T I O N 排序的。
在希尔排序中为什么在实现 h 有序时不使用选择排序？
对于部分有序的数组，插入排序比选择排序快。
这个结论可以在中文版 P158， 英文版 P252 找到。
将希尔排序中实时计算递增序列改为预先计算并存储在一个数组中。
希尔排序的官方实现：
只要稍作修改即可，详情见代码。
/// &summary&
/// 利用希尔排序将数组按升序排序。
/// &/summary&
/// &param name="a"&需要排序的数组。&/param&
public override void Sort&T&(T[] a)
int n = a.L
int[] h = new int[<span style="color: #];
// 预先准备好的 h 值数组
int hTemp = <span style="color: #;
int sequenceSize = <span style="color: #;
for (sequenceSize = <span style="color: #; hTemp & sequenceSize++)
if (sequenceSize &= h.Length)
// 如果数组不够大则双倍扩容
int[] expand = new int[h.Length * <span style="color: #];
for (int j = <span style="color: #; j & h.L j++)
expand[j] = h[j];
h[sequenceSize] = hT
hTemp = hTemp * <span style="color: # + <span style="color: #;
for (int t = sequenceSize - <span style="color: #; t &= <span style="color: #; t--)
for (int i = h[t]; i & i++)
for (int j = j &= h[t] && Less(a[j], a[j - h[t]]); j -= h[t])
Exch(a, j, j - h[t]);
Debug.Assert(IsHSorted(a, h[t]));
Debug.Assert(IsSorted(a));
令希尔排序打印出递增序列的每个元素所带来的比较次数和数组大小的比值。编写一个测试用例对随机 Double 数组进行希尔排序，验证该值是一个小常数，数组大小按照 10 的幂次递增，不小于 100。
结果截图如下，同一个 h 值对应的比值在数组大小不同时保持为一个小常数：
class Program
// 查看最后结果
// 可以发现相同的 h 在数组大小不同时所产生的比值十分接近。
static void Main(string[] args)
Random random = new Random();
ShellSort sort = new ShellSort();
int size = <span style="color: #0;
for (int i = <span style="color: #; i & <span style="color: #; i++)
double[] a = new double[size];
for (int j = <span style="color: #; j & j++)
a[j] = random.NextDouble() * <span style="color: #0;
Console.WriteLine("ArraySize:" + size);
sort.Sort(a);
size *= <span style="color: #;
纸牌排序。
说说你会如何将一副扑克牌按花色排序（花色排序是黑桃、红桃、梅花和方片），限制条件是所有牌都是背面朝上排成一列，而你一次只能翻看两张牌或者交换两张牌（保持背面朝上）。
可以用冒泡排序做，具体方法如下：
翻一二两张，是逆序对就交换，否则什么也不做
翻二三两张，是逆序对就交换，否则什么也不做
一直到最后，可以保证最右侧的是最大花色的牌
然后不断重复上述过程，就可以完全排序
出列顺序。
说说你会如何将一副扑克牌排序，限制条件是只能查看最上面的两张牌，交换最上面的两张牌，或是将最上面的一张牌放到这摞牌的最下面。
用一种类似于冒泡的方法做，具体步骤为：
重复以下步骤，直到全部完成一遍之后没有发生交换
重复以下步骤 n-<span style="color: # 次
如果顶端两张牌逆序，那么交换它们。
将第一张牌放到牌堆底部。
具体步骤图：
我们将牌排成一个环，用一支笔隔开，这里我们标记笔的左侧是牌堆顶部，右侧是牌堆底部。
那么我们能做的三个操作在这里即为：
查看最上面两张牌 = 从笔的位置开始，逆时针查看两张牌。
交换最上面两张牌 = 从笔的位置开始，逆时针选择两张牌并交换。
将最上面的一张牌放到最下面 = 将笔的位置逆时针移动一位。
下面我们开始执行开始说过的操作，目标顺序是自顶向下从小到大排列。
初始情况如图所示：
梅花7 和 红桃4 不是逆序对，直接将笔逆时针移动一位。
红桃4 和 黑桃6 不是逆序对，我们将笔逆时针移动一位。
再看 黑桃6 和 方片A，是逆序对，我们交换并将笔逆时针移动一位。
再看 黑桃6 和 红桃J，是逆序对，我们交换并将笔逆时针移动一位。
现在我们已经操作了 4 次，内部循环结束，我们将笔放回初始位置。
这样一次循环之后，我们就把最大的牌放在了最下面，依次类推即可完全排序。
昂贵的交换。
一家货运公司的一位职工得到了一项任务，需要将若干大货箱按照发货时间摆放。比较发货时间很容易（对照标签即可），但将两个货箱交换位置则很困难（移动麻烦）。仓库已经快满了，只有一个空闲的仓位。这位职员应该使用哪种排序算法呢？
交换（也就是 Exch() 方法）需要一个额外空间，这里的条件满足。
现在我们应该使交换次数最少，选择排序只需要 N 次交换，比插入排序平均 N^2/4 少（N & 2）。
编写一个 check() 方法，调用 sort() 对任意数组排序。如果排序成功而且数组中的所有对象均没有被修改则返回 true，否则返回 false。不要假设 sort() 只能通过 exch() 来移动数据，可以信任并使用 Array.sort()。
如果移动数据时新建了对象，那么虽然值没有改变，但是数组中的对象被修改了。
插入排序中的 Exch() 换成了如下方式：
string temp = new string(s[i].ToCharArray());
s[i] = s[min];
全部程序代码如下：
namespace _2._1._16
* 编写一个 check() 方法，
* 调用 sort() 对任意数组排序。
* 如果排序成功而且数组中的所有对象均没有被修改则返回 true，
* 否则返回 false。
* 不要假设 sort() 只能通过 exch() 来移动数据，
* 可以信任并使用 Array.sort()。
public class Program
static void Main(string[] args)
string[] test = new string[<span style="color: #] { "a", "b", "d", "c", "e" };
Console.WriteLine(CheckArraySort(test));
Console.WriteLine(CheckSelectionSort(test));
/// &summary&
/// 测试 Array.Sort() 方法。
/// &/summary&
/// &param name="a"&用于测试的数组。&/param&
/// &returns&如果数组对象没有改变，返回 true，否则返回 false。&/returns&
static bool CheckArraySort(string[] a)
string[] backup = new string[a.Length];
a.CopyTo(backup, <span style="color: #);
Array.Sort(a);
foreach (string n in a)
bool isFind = false;
for (int i = <span style="color: #; i & a.L i++)
if (ReferenceEquals(n, backup[i]))
isFind = true;
if (!isFind)
return false;
return true;
/// &summary&
/// 测试选择排序。
/// &/summary&
/// &param name="a"&用于测试的数组。&/param&
/// &returns&如果数组对象没有改变，返回 true，否则返回 false。&/returns&
static bool CheckSelectionSort(string[] a)
string[] backup = new string[a.Length];
a.CopyTo(backup, <span style="color: #);
SelectionSort(a);
foreach (string n in a)
bool isFind = false;
for (int i = <span style="color: #; i & a.L i++)
if (ReferenceEquals(n, backup[i]))
isFind = true;
if (!isFind)
return false;
return true;
/// &summary&
/// 选择排序，其中的交换部分使用新建对象并复制的方法。
/// &/summary&
/// &param name="s"&用于排序的数组。&/param&
public static void SelectionSort(string[] s)
for (int i = <span style="color: #; i & s.L i++)
for (int j = i + <span style="color: #; j & s.L j++)
if (s[j].CompareTo(s[min]) & <span style="color: #)
string temp = new string(s[i].ToCharArray());
s[i] = s[min];
修改插入排序和选择排序的代码，使之将数组内容绘制成正文中所示的棒状图。在每一轮排序后重绘图片来产生动画效果，并以一张“有序”的图片作为结束，即所有的圆棒均已按照高度有序排列。提示：使用类似于正文中的用例来随机生成 Double 值，在排序代码的适当位置调用 show() 方法，并在 show() 方法中清理画布并绘制棒状图。
选择排序：
插入排序：
使用一个 timer 按一定时间重绘数组，排序算法里面一次循环后等待一段时间再进行下一次循环。
这里排序算法是另开线程运行的，防止 Sleep 的时候让程序无响应。
选择排序：
using System.D
using System.Windows.F
using System.T
namespace _2._1._17
public partial class Form2 : Form
double[] randomD
public Form2(int N)
InitializeComponent();
this.randomDoubles = new double[N];
Random random = new Random();
for (int i = <span style="color: #; i & N; i++)
this.randomDoubles[i] = random.NextDouble() * <span style="color: #.8 + <span style="color: #.2;
drawPanel();
this.timer1.Interval = <span style="color: #;
this.timer1.Start();
Thread thread = new Thread(new ThreadStart(this.SelectionSort));
thread.IsBackground = true;
thread.Start();
/// &summary&
/// 选择排序。
/// &/summary&
private void SelectionSort()
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
for (int j = j & this.randomDoubles.L j++)
if (this.randomDoubles[min] & this.randomDoubles[j])
double temp = this.randomDoubles[i];
this.randomDoubles[i] = this.randomDoubles[min];
this.randomDoubles[min] =
Thread.Sleep(<span style="color: #00);
/// &summary&
/// 在屏幕上用柱形图绘制数组。
/// &/summary&
private void drawPanel()
Graphics graphics = this.CreateGraphics();
graphics.Clear(this.BackColor);
graphics.TranslateTransform(<span style="color: #, this.Height);
graphics.ScaleTransform(<span style="color: #, -<span style="color: #);
Rectangle clientRect = this.ClientR
Rectangle drawRect = new Rectangle(clientRect.X + <span style="color: #, clientRect.Y + <span style="color: #, clientRect.Width - <span style="color: #, clientRect.Height - <span style="color: #);
PointF[] barX = new PointF[this.randomDoubles.Length];
float unitX = (float)drawRect.Width / this.randomDoubles.L
unitX -= <span style="color: #;
barX[<span style="color: #] = new PointF(<span style="color: #, drawRect.Top);
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
barX[i] = new PointF(<span style="color: # + unitX + barX[i - <span style="color: #].X, drawRect.Top);
RectangleF[] bars = new RectangleF[this.randomDoubles.Length];
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
SizeF size = new SizeF(unitX, (float)this.randomDoubles[i] * drawRect.Height);
bars[i] = new RectangleF(barX[i], size);
graphics.FillRectangles(Brushes.Black, bars);
graphics.Dispose();
private void timer1_Tick(object sender, EventArgs e)
drawPanel();
插入排序：
using System.D
using System.Windows.F
using System.T
namespace _2._1._17
public partial class Form3 : Form
double[] randomD
public Form3(int N)
InitializeComponent();
this.randomDoubles = new double[N];
Random random = new Random();
for (int i = <span style="color: #; i & N; i++)
this.randomDoubles[i] = random.NextDouble() * <span style="color: #.8 + <span style="color: #.2;
drawPanel();
this.timer1.Interval = <span style="color: #;
this.timer1.Start();
Thread thread = new Thread(new ThreadStart(this.InsertionSort));
thread.IsBackground = true;
thread.Start();
/// &summary&
/// 插入排序。
/// &/summary&
private void InsertionSort()
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
for (int j = j & <span style="color: # && this.randomDoubles[j] & this.randomDoubles[j - <span style="color: #]; j--)
double temp = this.randomDoubles[j];
this.randomDoubles[j] = this.randomDoubles[j - <span style="color: #];
this.randomDoubles[j - <span style="color: #] =
Thread.Sleep(<span style="color: #0);
/// &summary&
/// 在屏幕上用柱形图绘制数组。
/// &/summary&
private void drawPanel()
Graphics graphics = this.CreateGraphics();
graphics.Clear(this.BackColor);
graphics.TranslateTransform(<span style="color: #, this.Height);
graphics.ScaleTransform(<span style="color: #, -<span style="color: #);
Rectangle clientRect = this.ClientR
Rectangle drawRect = new Rectangle(clientRect.X + <span style="color: #, clientRect.Y + <span style="color: #, clientRect.Width - <span style="color: #, clientRect.Height - <span style="color: #);
PointF[] barX = new PointF[this.randomDoubles.Length];
float unitX = (float)drawRect.Width / this.randomDoubles.L
unitX -= <span style="color: #;
barX[<span style="color: #] = new PointF(<span style="color: #, drawRect.Top);
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
barX[i] = new PointF(<span style="color: # + unitX + barX[i - <span style="color: #].X, drawRect.Top);
RectangleF[] bars = new RectangleF[this.randomDoubles.Length];
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
SizeF size = new SizeF(unitX, (float)this.randomDoubles[i] * drawRect.Height);
bars[i] = new RectangleF(barX[i], size);
graphics.FillRectangles(Brushes.Black, bars);
graphics.Dispose();
private void timer1_Tick(object sender, EventArgs e)
drawPanel();
可视轨迹。修改你为上一题给出的解答，为插入排序和选择排序生成和正文中类似的可视轨迹。提示：使用 setYscale() 函数是一个明智的选择。附加题：添加必要的代码，与正文中的图片一样用红色和灰色强调不同角色的元素。
与上题类似，但要特别标出移动的元素。
选择排序：
using System.D
using System.Windows.F
using System.T
namespace _2._1._18
public partial class Form2 : Form
double[] randomD
int sortI;
int sortJ;
public Form2(int N)
InitializeComponent();
this.randomDoubles = new double[N];
Random random = new Random();
for (int i = <span style="color: #; i & N; i++)
this.randomDoubles[i] = random.NextDouble() * <span style="color: #.8 + <span style="color: #.2;
/// &summary&
/// 选择排序。
/// &/summary&
private void SelectionSort()
for (this.sortI = <span style="color: #; this.sortI & this.randomDoubles.L this.sortI++)
this.sortMin = this.sortI;
for (this.sortJ = this.sortI; this.sortJ & this.randomDoubles.L this.sortJ++)
if (this.randomDoubles[this.sortMin] & this.randomDoubles[this.sortJ])
this.sortMin = this.sortJ;
drawPanel();
double temp = this.randomDoubles[this.sortI];
this.randomDoubles[this.sortI] = this.randomDoubles[this.sortMin];
this.randomDoubles[this.sortMin] =
Thread.Sleep(<span style="color: #00);
/// &summary&
/// 绘制柱形图。
/// &/summary&
private void drawPanel()
Graphics graphics = this.CreateGraphics();
graphics.Clear(this.BackColor);
graphics.TranslateTransform(<span style="color: #, this.Height);
graphics.ScaleTransform(<span style="color: #, -<span style="color: #);
Rectangle clientRect = this.ClientR
Rectangle drawRect = new Rectangle(clientRect.X + <span style="color: #, clientRect.Y + <span style="color: #, clientRect.Width - <span style="color: #, clientRect.Height - <span style="color: #);
PointF[] barX = new PointF[this.randomDoubles.Length];
float unitX = (float)drawRect.Width / this.randomDoubles.L
unitX -= <span style="color: #;
barX[<span style="color: #] = new PointF(<span style="color: #, drawRect.Top);
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
barX[i] = new PointF(<span style="color: # + unitX + barX[i - <span style="color: #].X, drawRect.Top);
RectangleF[] bars = new RectangleF[this.randomDoubles.Length];
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
SizeF size = new SizeF(unitX, (float)this.randomDoubles[i] * drawRect.Height);
bars[i] = new RectangleF(barX[i], size);
for (int i = <span style="color: #; i & bars.L i++)
if (i == this.sortMin)
graphics.FillRectangle(Brushes.Red, bars[i]);
else if (i & this.sortI)
graphics.FillRectangle(Brushes.Gray, bars[i]);
graphics.FillRectangle(Brushes.Black, bars[i]);
graphics.Dispose();
private void Form2_Shown(object sender, EventArgs e)
SelectionSort();
using System.D
using System.Windows.F
using System.T
namespace _2._1._18
public partial class Form3 : Form
double[] randomD
int sortI;
int sortJ;
int n = <span style="color: #;
public Form3(int N)
InitializeComponent();
this.randomDoubles = new double[N];
Random random = new Random();
for (int i = <span style="color: #; i & N; i++)
this.randomDoubles[i] = random.NextDouble() * <span style="color: #.8 + <span style="color: #.2;
/// &summary&
/// 插入排序。
/// &/summary&
private void InsertionSort()
for (this.sortI = <span style="color: #; this.sortI & this.randomDoubles.L this.sortI++)
for (this.sortJ = this.sortI; this.sortJ & <span style="color: # && this.randomDoubles[this.sortJ] & this.randomDoubles[this.sortJ - <span style="color: #]; this.sortJ--)
double temp = this.randomDoubles[this.sortJ];
this.randomDoubles[this.sortJ] = this.randomDoubles[this.sortJ - <span style="color: #];
this.randomDoubles[this.sortJ - <span style="color: #] =
drawPanel();
Thread.Sleep(<span style="color: #00);
/// &summary&
/// 绘制柱形图。
/// &/summary&
private void drawPanel()
Graphics graphics = this.CreateGraphics();
graphics.Clear(this.BackColor);
graphics.TranslateTransform(<span style="color: #, this.Height);
graphics.ScaleTransform(<span style="color: #, -<span style="color: #);
Rectangle clientRect = this.ClientR
Rectangle drawRect = new Rectangle(clientRect.X + <span style="color: #, clientRect.Y + <span style="color: #, clientRect.Width - <span style="color: #, clientRect.Height - <span style="color: #);
PointF[] barX = new PointF[this.randomDoubles.Length];
float unitX = (float)drawRect.Width / this.randomDoubles.L
unitX -= <span style="color: #;
barX[<span style="color: #] = new PointF(<span style="color: #, drawRect.Top);
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
barX[i] = new PointF(<span style="color: # + unitX + barX[i - <span style="color: #].X, drawRect.Top);
RectangleF[] bars = new RectangleF[this.randomDoubles.Length];
for (int i = <span style="color: #; i & this.randomDoubles.L i++)
SizeF size = new SizeF(unitX, (float)this.randomDoubles[i] * drawRect.Height);
bars[i] = new RectangleF(barX[i], size);
for (int i = <span style="color: #; i & bars.L i++)
if (i == this.sortJ)
graphics.FillRectangle(Brushes.Red, bars[i]);
else if (i &= this.sortI && i & this.sortJ)
graphics.FillRectangle(Brushes.Black, bars[i]);
graphics.FillRectangle(Brushes.Gray, bars[i]);
graphics.Dispose();
private void Form3_Shown(object sender, EventArgs e)
InsertionSort();
希尔排序的最坏情况。用 1 到 100 构造一个含有 100 个元素的数组并用希尔排序和递增序列 1 4 13 40 对其排序，使比较次数尽可能多。
不得不说这道题意外的难。
放上论文链接：
这篇论文的第二章给出了一种构造最坏序列的方法，当然理想最坏（n^(3/2)）是达不到的了。
最后结果是 793 次。
构造最坏情况的类
namespace _2._1._19
class ShellSortWorstCase
/// &summary&
/// 获得最坏情况的数组。
/// &/summary&
/// &param name="n"&数组大小。&/param&
/// &returns&希尔排序最坏情况的数组。&/returns&
public static int[] GetWorst(int n)
int l = <span style="color: #;
int?[] a = new int?[n + <span style="color: #];
for (int i = <span style="color: #; i & a.L i++)
a[i] = null;
int P = <span style="color: #;
int PAddition = P;
for (int i = <span style="color: #; l & <span style="color: #0; i++)
for (int j = <span style="color: #; j &= j++)
if (a[j] == null && IsVisible(j, P))
int[] b = new int[n];
for (int i = <span style="color: #; i & i++)
b[i] = (int)a[i + <span style="color: #];
/// &summary&
/// 确认 j - i 是不是在排序样板（Sorting Template）上。
/// &/summary&
/// &param name="i"&&/param&
/// &param name="j"&&/param&
/// &returns&&/returns&
public static bool IsVisible(int i, int j)
int k = <span style="color: #;
while (k &= <span style="color: #0)
if (j - i &= k * <span style="color: # && j - i &= k * <span style="color: #)
return true;
return false;
会显示比较次数的 ShellSort 类
using System.D
namespace _2._1._19
public class ShellSort : BaseSort
/// &summary&
/// 默认构造函数。
/// &/summary&
public ShellSort() { }
/// &summary&
/// 利用希尔排序将数组按升序排序。
/// &/summary&
/// &param name="a"&需要排序的数组。&/param&
public override void Sort&T&(T[] a)
int n = a.L
int compareTime = <span style="color: #;
int h = <span style="color: #;
while (h & n / <span style="color: #)
h = <span style="color: # * h + <span style="color: #;
while (h &= <span style="color: #)
for (int i = i & i++)
for (int j = j &= h && Less(a[j], a[j - h]); j -= h)
Exch(a, j, j - h);
compareTime++;
compareTime++;
Debug.Assert(IsHSorted(a, h));
h /= <span style="color: #;
Console.WriteLine("CompareTime:" + compareTime);
Debug.Assert(IsSorted(a));
/// &summary&
/// 检查一次希尔排序后的子数组是否有序。
/// &/summary&
/// &param name="a"&排序后的数组。&/param&
/// &param name="h"&子数组间隔。&/param&
/// &returns&是否有序。&/returns&
private bool IsHSorted&T&(T[] a, int h) where T : IComparable&T&
for (int i = i & a.L i++)
if (Less(a[i], a[i - h]))
return false;
return true;
namespace _2._1._19
* 希尔排序的最坏情况。
* 用 1 到 100 构造一个含有 100 个元素的数组并用希尔排序和
* 递增序列 1 4 13 40 对其排序，
* 使比较次数尽可能多。
class Program
// 开放题，没有标准答案
// 共参考的最差情况为 n^(3/2)
// 本例共 793 次
static void Main(string[] args)
ShellSort sort = new ShellSort();
b = ShellSortWorstCase.GetWorst(<span style="color: #0);
for (int i = <span style="color: #; i & b.L i++)
Console.Write(b[i] + " ");
Console.WriteLine();
sort.Sort(b);
希尔排序的最好情况。最好情况是什么？证明你的结论。
由于每次 h 排序都是插入排序，希尔排序最好情况就是插入排序的最好情况，也就是已排序的数组。
可比较的交易。用我们的 Date 类（请见 2.1.1.4 节）作为模板扩展你的 Transaction 类（请见练习 1.2.13），实现 Comparable 接口，使交易能够按照金额排序。
事实上官方给出来的 Date 类以及 Transaction 类都已经实现了这些接口。
Transaction 类：
namespace _2._1._21
* 可比较的交易。
* 用我们的 Date 类（请见 2.1.1.4 节）
* 作为模板扩展你的 Transaction 类（请见练习 1.2.13），
* 实现 Comparable 接口，使交易能够按照金额排序。
class Program
static void Main(string[] args)
Transaction[] a = new Transaction[<span style="color: #];
a[<span style="color: #] = new Transaction("Turing 6/17/");
a[<span style="color: #] = new Transaction("Tarjan 3/26/");
a[<span style="color: #] = new Transaction("Knuth 6/14/");
a[<span style="color: #] = new Transaction("Dijkstra 8/22/");
Console.WriteLine("Unsorted");
for (int i = <span style="color: #; i & a.L i++)
Console.WriteLine(a[i]);
Console.WriteLine();
Console.WriteLine("Sort by amount");
InsertionSort insertionSort = new InsertionSort();
insertionSort.Sort(a, new Transaction.HowMuchOrder());
for (int i = <span style="color: #; i & a.L i++)
Console.WriteLine(a[i]);
Console.WriteLine();
交易排序测试用例。编写一个 SortTransaction 类，在静态方法 main() 中从标准输入读取一系列交易，将它们排序并在标准输出中打印结果。
和上题类似，只要传入事先写好的比较器就可以了。
namespace _2._1._22
* 交易排序测试用例。
* 编写一个 SortTransaction 类，
* 在静态方法 main() 中从标准输入读取一系列交易，
* 将它们排序并在标准输出中打印结果。
class Program
static void Main(string[] args)
Transaction[] a = new Transaction[<span style="color: #];
// 样例输入
// Turing 6/17/
// Tarjan 3/26/
// Knuth 6/14/
// Dijkstra 8/22/
for (int i = <span style="color: #; i & a.L i++)
string input = Console.ReadLine();
a[i] = new Transaction(input);
InsertionSort insertionSort = new InsertionSort();
Console.WriteLine("Unsorted");
for (int i = <span style="color: #; i & a.L i++)
Console.WriteLine(a[i]);
Console.WriteLine();
Console.WriteLine("Sort by date");
insertionSort.Sort(a, new Transaction.WhenOrder());
for (int i = <span style="color: #; i & a.L i++)
Console.WriteLine(a[i]);
Console.WriteLine();
Console.WriteLine("Sort by customer");
insertionSort.Sort(a, new Transaction.WhoOrder());
for (int i = <span style="color: #; i & a.L i++)
Console.WriteLine(a[i]);
Console.WriteLine();
Console.WriteLine("Sort by amount");
insertionSort.Sort(a, new Transaction.HowMuchOrder());
for (int i = <span style="color: #; i & a.L i++)
Console.WriteLine(a[i]);
Console.WriteLine();
纸牌排序。请几位朋友分别将一副扑克牌排序（见练习2.1.13）。仔细观察并记录他们所使用的方法。
方法多种多样。
首先是冒泡，见习题 2.1.13
插入排序也可以，如下：&&&&& 从前往后不断翻牌，&&&&& 对于翻到的每张牌，一直和之前的牌交换，&&&&& 直至前面的牌比它小或者它已经是第一张了。
也可以用基数排序&&&&& 从前向后依次翻开牌，&&&&& 按照花色分成四堆，&&&&& 然后按花色从大到小重新排列。
比较符合直觉的是选择排序&&&&& 寻找最小的牌并放到第一位，&&&&& 寻找范围向右缩减一位，重复上一步，直到最后一张。
还有其他方法，这里不再赘述。
插入排序的哨兵。在插入排序的实现中先找出最小的元素并将其置于数组的最左边，这样就能去掉内循环的判断条件 j&0。使用 SortCompare 来评估这种做法的效果。注意：这是一种常见的规避边界测试的方法，能够省略判断条件的元素通常称为哨兵。
如果使用官方的实现（），最后结果可能会比一般插入排序慢，因为它是用冒泡的方法找最小值的。
一般做法是在待排序数组的最前端插入一个很小的值（比如 int.MinValue），然后对 a[1]~a[n] 排序。
参考官方实现的插入排序：
using System.Collections.G
using System.D
namespace _2._1._24
/// &summary&
/// 插入排序类。
/// &/summary&
public class InsertionSort : BaseSort
/// &summary&
/// 默认构造函数。
/// &/summary&
public InsertionSort() { }
/// &summary&
/// 利用插入排序将数组按升序排序。
/// &/summary&
/// &param name="a"&需要排序的数组。&/param&
public override void Sort&T&(T[] a)
int n = a.L
int exchanges = <span style="color: #;
for (int i = n - <span style="color: #; i & <span style="color: #; i--)
if (Less(a[i], a[i - <span style="color: #]))
Exch(a, i, i - <span style="color: #);
exchanges++;
if (exchanges == <span style="color: #)
for (int i = <span style="color: #; i & i++)
for (int j = Less(a[j], a[j - <span style="color: #]); --j)
Exch(a, j, j - <span style="color: #);
Debug.Assert(IsSorted(a, <span style="color: #, i));
Debug.Assert(IsSorted(a));
/// &summary&
/// 利用插入排序将数组排序。（使用指定比较器）
/// &/summary&
/// &typeparam name="T"&数组元素类型。&/typeparam&
/// &param name="a"&需要排序的数组。&/param&
/// &param name="c"&比较器。&/param&
public void Sort&T&(T[] a, IComparer&T& c)
int n = a.L
int exchanges = <span style="color: #;
for (int i = n - <span style="color: #; i & <span style="color: #; i--)
if (Less(a[i], a[i - <span style="color: #], c))
Exch(a, i, i - <span style="color: #);
exchanges++;
if (exchanges == <span style="color: #)
for (int i = <span style="color: #; i & i++)
for (int j = Less(a[j], a[j - <span style="color: #], c); --j)
Exch(a, j, j - <span style="color: #);
Debug.Assert(IsSorted(a, <span style="color: #, i, c));
Debug.Assert(IsSorted(a, c));
不需要交换的插入排序。在插入排序的实现中使较大元素右移一位只需要访问一次数组（而不用使用 exch()）。使用 SortCompare 来评估这种做法的效果。
使用依次赋值的方式腾出空间，到达指定位置之后再把元素插入。
看代码会方便理解一点。
官方实现：。
using System.Collections.G
using System.D
namespace _2._1._25
/// &summary&
/// 插入排序类。
/// &/summary&
public class InsertionSort : BaseSort
/// &summary&
/// 默认构造函数。
/// &/summary&
public InsertionSort() { }
/// &summary&
/// 利用插入排序将数组按升序排序。
/// &/summary&
/// &param name="a"&需要排序的数组。&/param&
public override void Sort&T&(T[] a)
int n = a.L
int exchanges = <span style="color: #;
for (int i = n - <span style="color: #; i & <span style="color: # ; i--)
if (Less(a[i], a[i - <span style="color: #]))
Exch(a, i, i - <span style="color: #);
exchanges++;
if (exchanges == <span style="color: #)
for (int i = <span style="color: #; i & i++)
T v = a[i];
while (Less(v, a[j - <span style="color: #]))
a[j] = a[j - <span style="color: #];
Debug.Assert(IsSorted(a, <span style="color: #, i));
Debug.Assert(IsSorted(a));
/// &summary&
/// 利用插入排序将数组排序。（使用指定比较器）
/// &/summary&
/// &typeparam name="T"&数组元素类型。&/typeparam&
/// &param name="a"&需要排序的数组。&/param&
/// &param name="c"&比较器。&/param&
public void Sort&T&(T[] a, IComparer&T& c)
int n = a.L
int exchanges = <span style="color: #;
for (int i = n - <span style="color: #; i & <span style="color: #; i--)
if (Less(a[i], a[i - <span style="color: #], c))
Exch(a, i, i - <span style="color: #);
exchanges++;
if (exchanges == <span style="color: #)
for (int i = <span style="color: #; i & i++)
T v = a[i];
while (Less(v, a[j - <span style="color: #], c))
a[j] = a[j - <span style="color: #];
Debug.Assert(IsSorted(a, <span style="color: #, i, c));
Debug.Assert(IsSorted(a, c));
原始数据类型。编写一个能够处理 int 值的插入排序的新版本，比较它和正文中所给出的实现（能够隐式地用自动装箱和拆箱转换 Integer 值并排序）的性能。
直接针对特殊值的话显然会快很多。
直接把泛型改成 int 即可。
namespace _2._1._26
/// &summary&
/// 插入排序类。
/// &/summary&
public class InsertionSort
/// &summary&
/// 默认构造函数。
/// &/summary&
public InsertionSort() { }
/// &summary&
/// 利用插入排序将数组按升序排序。
/// &/summary&
/// &param name="a"&需要排序的数组。&/param&
public void Sort(int[] a)
int n = a.L
for (int i = <span style="color: #; i & i++)
for (int j = j & <span style="color: # && a[j] & a[j - <span style="color: #]; --j)
int t = a[j];
a[j] = a[j - <span style="color: #];
a[j - <span style="color: #] =
希尔排序的用时是次平方级的。在你的计算机上用 SortCompare 比较希尔排序和插入排序以及选择排序。测试数组的大小按照 2 的幂次递增，从 128 开始。
数据比较大的时候会比较明显。
namespace _2._1._27
* 希尔排序的用时是次平方级的。
* 在你的计算机上用 SortCompare 比较希尔排序和插入排序以及选择排序。
* 测试数组的大小按照 2 的幂次递增，从 128 开始。
class Program
static void Main(string[] args)
int n = <span style="color: #8;
Random random = new Random();
double shellPrev = <span style="color: #;
double insertionPrev = <span style="color: #;
double selectionPrev = <span style="color: #;
while (n & <span style="color: #538)
int[] testShell = new int[n];
int[] testInsertion = new int[n];
int[] testSelection = new int[n];
for (int i = <span style="color: #; i & i++)
testShell[i] = random.Next();
testInsertion[i] = testShell[i];
testSelection[i] = testShell[i];
Console.WriteLine("数组大小：" + n);
Console.Write("Shell Sort:");
double shellNow = SortCompare.Time(new ShellSort(), testShell);
Console.WriteLine(shellNow + "\t\tNow/Prev=" + shellNow / shellPrev);
Console.Write("Insertion Sort:");
double insertionNow = SortCompare.Time(new InsertionSort(), testInsertion);
Console.WriteLine(insertionNow + "\tNow/Prev=" + insertionNow / insertionPrev);
Console.Write("Selection Sort:");
double selectionNow = SortCompare.Time(new SelectionSort(), testSelection);
Console.WriteLine(selectionNow + "\tNow/Prev=" + selectionNow / selectionPrev);
Console.WriteLine();
shellPrev = shellN
insertionPrev = insertionN
selectionPrev = selectionN
n *= <span style="color: #;
相等的主键。对于主键仅可能取两种值的数组，评估和验证插入排序和选择排序的性能，假设两种主键值出现的概率相同。
插入排序会比选择排序快上许多，当然增长级别不变。
namespace _2._1._28
* 相等的主键。
* 对于主键仅可能取两种值的数组，
* 评估和验证插入排序和选择排序的性能，
* 假设两种主键值出现的概率相同。
class Program
static void Main(string[] args)
int n = <span style="color: #24;
Random random = new Random();
double insertionPrev = <span style="color: #;
double selectionPrev = <span style="color: #;
while (n & <span style="color: #538)
int[] testInsertion = new int[n];
int[] testSelection = new int[n];
for (int i = <span style="color: #; i & i++)
testInsertion[i] = random.Next(<span style="color: #);
testSelection[i] = testInsertion[i];
Console.WriteLine("数组大小：" + n);
Console.Write("Insertion Sort:");
double insertionNow = SortCompare.Time(new InsertionSort(), testInsertion);
Console.WriteLine(insertionNow + "\tNow/Prev=" + insertionNow / insertionPrev);
Console.Write("Selection Sort:");
double selectionNow = SortCompare.Time(new SelectionSort(), testSelection);
Console.WriteLine(selectionNow + "\tNow/Prev=" + selectionNow / selectionPrev);
Console.WriteLine();
insertionPrev = insertionN
selectionPrev = selectionN
n *= <span style="color: #;
希尔排序的递增序列。通过实验比较算法 2.3 中所使用的递增序列和递增序列 1, 5, 19, 41, 109, 209, 505, 929, , , 3, 0609 （这是通过序列 9×4^(k)-9×2^(k)+1 和 4^(k)-3×2^(k)+1 综合得到的）。可以参考练习 2.1.11。
当然是题目给出的递增序列更快啦，因为这个序列就是作者提出来的嘛。（论文链接： ）
修改了一下 shellsort，让它按照给定的 h 序列排序。
using System.D
namespace _2._1._29
public class ShellSort : BaseSort
/// &summary&
/// 默认构造函数。
/// &/summary&
public ShellSort() { }
/// &summary&
/// 利用希尔排序将数组按升序排序。
/// &/summary&
/// &typeparam name="T"&待排序的元素类型。&/typeparam&
/// &param name="a"&待排序的数组。&/param&
/// &param name="h"&需要使用的递增序列。&/param&
public void Sort&T&(T[] a, int[] h) where T : IComparable&T&
int n = a.L
int t = <span style="color: #;
while (h[t] & a.Length)
if (t &= h.Length)
for ( ; t &= <span style="color: #; t--)
for (int i = h[t]; i & i++)
for (int j = j &= h[t] && Less(a[j], a[j - h[t]]); j -= h[t])
Exch(a, j, j - h[t]);
Debug.Assert(IsHSorted(a, h[t]));
Debug.Assert(IsSorted(a));
/// &summary&
/// 利用希尔排序将数组按升序排序。
/// &/summary&
/// &param name="a"&需要排序的数组。&/param&
public override void Sort&T&(T[] a)
int n = a.L
int[] h = new int[<span style="color: #];
// 预先准备好的 h 值数组
int hTemp = <span style="color: #;
int sequenceSize = <span style="color: #;
for (sequenceSize = <span style="color: #; hTemp & sequenceSize++)
if (sequenceSize &= h.Length)
// 如果数组不够大则双倍扩容
int[] expand = new int[h.Length * <span style="color: #];
for (int j = <span style="color: #; j & h.L j++)
expand[j] = h[j];
h[sequenceSize] = hT
hTemp = hTemp * <span style="color: # + <span style="color: #;
for (int t = sequenceSize - <span style="color: #; t &= <span style="color: #; t--)
for (int i = h[t]; i & i++)
for (int j = j &= h[t] && Less(a[j], a[j - h[t]]); j -= h[t])
Exch(a, j, j - h[t]);
Debug.Assert(IsHSorted(a, h[t]));
Debug.Assert(IsSorted(a));
/// &summary&
/// 检查一次希尔排序后的子数组是否有序。
/// &/summary&
/// &param name="a"&排序后的数组。&/param&
/// &param name="h"&子数组间隔。&/param&
/// &returns&是否有序。&/returns&
private bool IsHSorted&T&(T[] a, int h) where T : IComparable&T&
for (int i = i & a.L i++)
if (Less(a[i], a[i - h]))
return false;
return true;
几何级数递增序列。通过实验找到一个 t，使得对于大小为 N=10^6 的任意随机数组，使用递增序列 1, [t], [t^2], [t^3], [t^4], ... 的希尔排序的运行时间最短。给出你能找到的三个最佳 t 值以及相应的递增序列。以下练习描述的是各种用于评估排序算法的测试用例。它们的作用是用随机数据帮助你增进对性能特性的理解。随着命令行指定的实验测试的增大，可以和 SortCompare 一样在它们中使用 time() 函数来得到更精确的结果。在以后的几节中我们会使用这些练习来评估更为复杂的算法。
t 越大的话，按照这个递增序列，10^6 次能够满足的 h 也就越少。
using System.D
namespace _2._1._30
* 几何级数递增序列。
* 通过实验找到一个 t，使得对于大小为 N=10^6 的任意随机数组，
* 使用递增序列 1, [t], [t^2], [t^3], [t^4], ... 的希尔排序的运行时间最短。
* 给出你能找到的三个最佳 t 值以及相应的递增序列。
* 以下练习描述的是各种用于评估排序算法的测试用例。
* 它们的作用是用随机数据帮助你增进对性能特性的理解。
* 随着命令行指定的实验测试的增大，
* 可以和 SortCompare 一样在它们中使用 time() 函数来得到更精确的结果。
* 在以后的几节中我们会使用这些练习来评估更为复杂的算法。
class Program
// t = 2, 3, 4
// t 大于 10 之后，由于每次排序 h 缩减的太快，
// 时间会越来越近似于直接插入排序。
static void Main(string[] args)
int[] array = SortCompare.GetRandomArrayInt(<span style="color: #00000);
int[] array2 = new int[array.Length];
array.CopyTo(array2, <span style="color: #);
Stopwatch timer = new Stopwatch();
long[] bestTimes = new long[<span style="color: #];
long[] bestTs = new long[<span style="color: #];
for (int i = <span style="color: #; i & bestTimes.L i++)
bestTimes[i] = long.MaxV
bestTs[i] = int.MaxV
long nowTime = <span style="color: #;
ShellSort shellSort = new ShellSort();
for (int t = <span style="color: #; t &= <span style="color: #00000; t++)
Console.WriteLine(t);
timer.Restart();
shellSort.Sort(array, t);
nowTime = timer.ElapsedM
timer.Stop();
Console.WriteLine("Elapsed Time:" + nowTime);
for (int i = <span style="color: #; i & bestTimes.L i++)
Console.Write("t:" + bestTs[i]);
Console.WriteLine("\tTime:" + bestTimes[i]);
if (bestTimes[<span style="color: #] & nowTime)
bestTimes[<span style="color: #] = nowT
bestTs[<span style="color: #] =
Array.Sort(bestTimes, bestTs);
array2.CopyTo(array, <span style="color: #);
for (int i = <span style="color: #; i & bestTimes.L i++)
Console.Write("t:" + bestTs[i]);
Console.Write("\tTime:" + bestTimes[i]);
双倍测试。编写一个能够对排序算法进行双倍测试的用例。数组规模 N 的起始值为 1000，排序后打印 N、估计排序用时、实际排序用时以及在 N 倍增之后两次用时的比例。用这段程序验证在随机输入模型下插入排序和选择排序的运行时间都是平方级别的。对希尔排序的性能做出猜想并验证你的猜想。
这里截取数据量比较大的时候的数据。
插入排序和选择排序显然都是平方级别的。
希尔排序猜测是线性的，实际上要比线性大一点（次平方级）。
namespace _2._1._31
* 双倍测试。
* 编写一个能够对排序算法进行双倍测试的用例。
* 数组规模 N 的起始值为 1000，
* 排序后打印 N、估计排序用时、实际排序用时以及在 N 倍增之后两次用时的比例。
* 用这段程序验证在随机输入模型下插入排序和选择排序的运行时间都是平方级别的。
* 对希尔排序的性能做出猜想并验证你的猜想。
class Program
static void Main(string[] args)
int N = <span style="color: #00;
InsertionSort insertion = new InsertionSort();
SelectionSort selection = new SelectionSort();
ShellSort shell = new ShellSort();
double prevInsertion = <span style="color: #;
double prevSelection = <span style="color: #;
double prevShell = <span style="color: #;
for (int i = <span style="color: #; i & <span style="color: #; i++)
Console.WriteLine("N:" + N);
int[] array = SortCompare.GetRandomArrayInt(N);
int[] arrayBak = new int[N];
array.CopyTo(arrayBak, <span style="color: #);
Console.WriteLine("\tInsertion Sort");
double now = SortCompare.Time(insertion, array);
Console.WriteLine("\t\tActual Time(ms):" + now);
if (i != <span style="color: #)
Console.WriteLine("\t\tEstimate Time(ms):" + prevInsertion * <span style="color: #);
Console.WriteLine("\t\tRatio:" + now / prevInsertion);
prevInsertion =
arrayBak.CopyTo(array, <span style="color: #);
Console.WriteLine("\tSelection Sort");
now = SortCompare.Time(selection, array);
Console.WriteLine("\t\tActual Time(ms):" + now);
if (i != <span style="color: #)
Console.WriteLine("\t\tEstimate Time(ms):" + prevSelection * <span style="color: #);
Console.WriteLine("\t\tRatio:" + now / prevSelection);
prevSelection =
arrayBak.CopyTo(array, <span style="color: #);
Console.WriteLine("\tShell Sort");
now = SortCompare.Time(shell, array);
Console.WriteLine("\t\tActual Time(ms):" + now);
if (i != <span style="color: #)
Console.WriteLine("\t\tEstimate Time(ms):" + prevShell * <span style="color: #);
Console.WriteLine("\t\tRatio:" + now / prevShell);
prevShell =
N *= <span style="color: #;
运行时间曲线图。编写一个测试用例，使用 StdDraw 在各种不同规模的随机输入下将算法的平均运行时间绘制成一张曲线图。可能需要添加一两个命令行参数，请尽量设计一个实用的工具。
基本上都是这么个样子：
using System.D
using System.L
using System.Windows.F
namespace _2._1._32
public partial class Form2 : Form
/// &summary&
/// 构造一个绘图结果窗口。
/// &/summary&
/// &param name="sort"&用于做测试的排序算法。&/param&
/// &param name="n"&用于测试的初始数据量。&/param&
public Form2(BaseSort sort, int n)
InitializeComponent();
this.sort =
this.result = Test(n);
this.timer1.Interval = <span style="color: #00;
this.timer1.Start();
/// &summary&
/// 执行八次耗时测试，每次数据量翻倍。
/// &/summary&
/// &param name="n"&初始数据量。&/param&
/// &returns&测试结果数据。&/returns&
public double[] Test(int n)
double[] result = new double[<span style="color: #];
for (int i = <span style="color: #; i & result.L i++)
result[i] = SortCompare.TimeRandomInput(this.sort, n, <span style="color: #);
n *= <span style="color: #;
/// &summary&
/// 绘制曲线图。
/// &/summary&
/// &param name="result"&结果数组。&/param&
public void DrawPanel(double[] result)
Graphics graphics = this.CreateGraphics();
graphics.TranslateTransform(<span style="color: #, this.ClientRectangle.Height);
graphics.ScaleTransform(<span style="color: #, -<span style="color: #);
Rectangle clientRect = this.ClientR
Rectangle drawRect = new Rectangle(clientRect.X + <span style="color: #, clientRect.Y + <span style="color: #, clientRect.Width - <span style="color: #, clientRect.Height - <span style="color: #);
PointF[] dataPoints = new PointF[result.Length];
float unitX = (float)drawRect.Width / result.L
float unitY = (float)(drawRect.Height / result.Max());
SizeF pointSize = new SizeF(<span style="color: #, <span style="color: #);
for (int i = <span style="color: #; i & result.L i++)
dataPoints[i] = new PointF(drawRect.Left + unitX * i, (float)(unitY * result[i]));
graphics.FillEllipse(Brushes.Black, new RectangleF(dataPoints[i], pointSize));
private void timer1_Tick(object sender, EventArgs e)
DrawPanel(this.result);
this.timer1.Stop();
分布图。对于你为练习 2.1.33 给出的测试用例，在一个无穷循环中调用 sort() 方法将由第三个命令行参数指定大小的数组排序，记录每次排序的用时并使用 StdDraw 在图上画出所有平均运行时间，应该能够得到一张运行时间的分布图。
这里每次结果的 Y 轴位置都是随机生成的，这样图像会好看点。
X 轴代表消耗的时间。
选择排序：
插入排序：
希尔排序：
using System.Collections.G
using System.D
using System.L
using System.Windows.F
namespace _2._1._33
public partial class Form2 : Form
List&double& resultL
List&float& resultYL
Rectangle clientR
Rectangle drawR
/// &summary&
/// 构造一个绘制结果窗口。
/// &/summary&
/// &param name="sort"&用于测试的排序算法。&/param&
/// &param name="n"&测试算法是生成的数据量。&/param&
public Form2(BaseSort sort, int n)
InitializeComponent();
this.resultList = new List&double&();
this.resultYList = new List&float&();
this.clientRect = this.ClientR
this.drawRect = new Rectangle(this.clientRect.X + <span style="color: #, this.clientRect.Y + <span style="color: #, this.clientRect.Width - <span style="color: #, this.clientRect.Height - <span style="color: #);
this.sort =
this.timer1.Interval = <span style="color: #0;
this.timer1.Start();
/// &summary&
/// 执行一次测试并绘制图像。
/// &/summary&
public void Test()
Random random = new Random();
double[] array = SortCompare.GetRandomArrayDouble(this.n);
double time = SortCompare.Time(this.sort, array);
this.resultList.Add(time);
this.resultYList.Add((float)(random.NextDouble() * this.drawRect.Height));
DrawPanel(this.resultList.ToArray(), this.resultYList.ToArray());
/// &summary&
/// 根据已有的数据绘制图像。
/// &/summary&
/// &param name="result"&耗时数据（X 轴）&/param&
/// &param name="resultY"&Y 轴数据&/param&
public void DrawPanel(double[] result, float[] resultY)
Graphics graphics = this.CreateGraphics();
graphics.Clear(this.BackColor);
graphics.TranslateTransform(<span style="color: #, this.ClientRectangle.Height);
graphics.ScaleTransform(<span style="color: #, -<span style="color: #);
PointF[] dataPoints = new PointF[result.Length];
float unitX = (float)(this.drawRect.Width / (result.Max() - result.Min()));
double min = result.Min();
SizeF pointSize = new SizeF(<span style="color: #, <span style="color: #);
for (int i = <span style="color: #; i & result.L i++)
dataPoints[i] = new PointF((float)(unitX * (result[i] - min)), resultY[i]);
graphics.FillEllipse(Brushes.Black, new RectangleF(dataPoints[i], pointSize));
private void timer1_Tick(object sender, EventArgs e)
罕见情况。编写一个测试用例，调用 sort() 方法对实际应用中可能出现困难或极端情况的数组进行排序。比如，数组可能已经是有序的，或是逆序的，数组中的所有主键相同，数组的主键只有两种值，大小是 0 或 1的数组。
namespace _2._1._34
* 罕见情况。
* 编写一个测试用例，
* 调用 sort() 方法对实际应用中可能出现困难或极端情况的数组进行排序。
* 比如，数组可能已经是有序的，
* 或是逆序的，
* 数组中的所有主键相同，
* 数组的主键只有两种值，
* 大小是 0 或 1 的数组。
class Program
static void Main(string[] args)
InsertionSort insertionSort = new InsertionSort();
SelectionSort selectionSort = new SelectionSort();
ShellSort shellSort = new ShellSort();
Console.WriteLine("逆序");
Console.WriteLine("Insertion Sort Time: " + ReverseSortTest(insertionSort));
Console.WriteLine("Selection Sort Time: " + ReverseSortTest(selectionSort));
Console.WriteLine("Shell Sort Time: " + ReverseSortTest(shellSort));
Console.WriteLine("顺序");
Console.WriteLine("Insertion Sort Time: " + SortedSortTest(insertionSort));
Console.WriteLine("Selection Sort Time: " + SortedSortTest(selectionSort));
Console.WriteLine("Shell Sort Time: " + SortedSortTest(shellSort));
// 主键相同
Console.WriteLine("主键相同");
Console.WriteLine("Insertion Sort Time: " + EqualSortTest(insertionSort));
Console.WriteLine("Selection Sort Time: " + EqualSortTest(selectionSort));
Console.WriteLine("Shell Sort Time: " + EqualSortTest(shellSort));
// 二元数组
Console.WriteLine("二元数组");
Console.WriteLine("Insertion Sort Time: " + BinarySortTest(insertionSort));
Console.WriteLine("Selection Sort Time: " + BinarySortTest(selectionSort));
Console.WriteLine("Shell Sort Time: " + BinarySortTest(shellSort));
Console.WriteLine("空数组");
Console.WriteLine("Insertion Sort Time: " + ZeroArraySizeSort(insertionSort));
Console.WriteLine("Selection Sort Time: " + ZeroArraySizeSort(selectionSort));
Console.WriteLine("Shell Sort Time: " + ZeroArraySizeSort(shellSort));
// 只有一个元素的数组
Console.WriteLine("只有一个元素的数组");
Console.WriteLine("Insertion Sort Time: " + OneArraySizeSort(insertionSort));
Console.WriteLine("Selection Sort Time: " + OneArraySizeSort(selectionSort));
Console.WriteLine("Shell Sort Time: " + OneArraySizeSort(shellSort));
/// &summary&
/// 构造逆序数组并用其对指定输入算法进行测试。
/// &/summary&
/// &param name="sort"&需要做测试的算法。&/param&
/// &returns&算法耗时。&/returns&
static double ReverseSortTest(BaseSort sort)
int[] array = new int[<span style="color: #000];
for (int i = <span style="color: #; i & array.L i++)
array[i] = array.Length -
return SortCompare.Time(sort, array);
/// &summary&
/// 构造已排序的数组并用其对指定排序算法测试。
/// &/summary&
/// &param name="sort"&需要做测试的排序算法。&/param&
/// &returns&算法的耗时。&/returns&
static double SortedSortTest(BaseSort sort)
return SortCompare.TimeSortedInput(sort, <span style="color: #000, <span style="color: #);
/// &summary&
/// 构造只有一个值的数组并用其对指定排序算法做测试。
/// &/summary&
/// &param name="sort"&需要做测试的排序算法。&/param&
/// &returns&算法的耗时。&/returns&
static double EqualSortTest(BaseSort sort)
int[] array = new int[<span style="color: #000];
Random random = new Random();
int num = random.Next();
for (int i = <span style="color: #; i & array.L i++)
array[i] =
return SortCompare.Time(sort, array);
/// &summary&
/// 构造只有两种取值的数组并用其对指定排序算法做测试。
/// &/summary&
/// &param name="sort"&需要做测试的排序算法。&/param&
/// &returns&排序算法的耗时。&/returns&
static double BinarySortTest(BaseSort sort)
int[] array = new int[<span style="color: #000];
Random random = new Random();
for (int i = <span style="color: #; i & array.L i++)
array[i] = random.Next(<span style="color: #);
return SortCompare.Time(sort, array);
/// &summary&
/// 构造空数组并用其对指定排序算法做测试。
/// &/summary&
/// &param name="sort"&需要做测试的排序算法。&/param&
/// &returns&排序算法的耗时。&/returns&
static double ZeroArraySizeSort(BaseSort sort)
int[] array = new int[<span style="color: #];
return SortCompare.Time(sort, array);
/// &summary&
/// 构造只有一个元素的数组并用其对指定排序算法做测试。
/// &/summary&
/// &param name="sort"&需要做测试的排序算法。&/param&
/// &returns&排序算法的耗时。&/returns&
static double OneArraySizeSort(BaseSort sort)
int[] array = new int[<span style="color: #];
Random random = new Random();
array[<span style="color: #] = random.Next();
return SortCompare.Time(sort, array);
不均匀的概率分布。编写一个测试用例，使用非均匀分布的概率来生成随机排列的数据，包括：
离散分布（一种特殊情况见练习 2.1.28）。
评估并验证这些输入数据对本节讨论的算法的影响。
难点是如何生成符合这些分布的随机数。
Java 的话官方给的 stdRandom 里面都有相应的实现。
几种随机数的实现：
namespace Sort
/// &summary&
/// 静态类，包含用于生成排序算法测试数据的方法。
/// &/summary&
public static class SortUtil
public static Random UniformGenerator = new Random();
/// &summary&
/// 产生符合正态分布的随机数。
/// &/summary&
/// &param name="average"&正态分布的期望值 μ。&/param&
/// &param name="standardDeviation"&正态分布的标准差 σ。&/param&
/// &returns&符合正态分布的随机数。&/returns&
public static double Normal(double average, double standardDeviation)
double u1 = UniformGenerator.NextDouble();
double u2 = UniformGenerator.NextDouble();
double z0 = Math.Sqrt(-<span style="color: #.0 * Math.Log(u1)) * Math.Cos(Math.PI * <span style="color: # * u2);
return z0 * standardDeviation +
/// &summary&
/// 生成符合泊松分布的随机数。
/// &/summary&
/// &param name="average"&泊松分布的期望值 λ。&/param&
/// &returns&一个符合泊松分布的随机数。&/returns&
public static double Poission(double average)
double x = <span style="color: #;
double p = Math.Pow(Math.E, -average);
double s =
double u = UniformGenerator.NextDouble();
p *= average /
} while (u & s);
/// &summary&
/// 生成符合几何分布的随机数。
/// &/summary&
/// &param name="p"&几何分布的概率 p，这应该是一个小于 1 的非负数。&/param&
/// &exception cref="ArgumentOutOfRangeException"&概率不能大于 1.&/exception&
/// &returns&符合几何分布的随机数。&/returns&
public static double Geometry(double p)
if (p & <span style="color: #)
throw new ArgumentOutOfRangeException("p", "概率不能大于 1");
result = Math.Ceiling(Math.Log(<span style="color: # - UniformGenerator.NextDouble()) / Math.Log(<span style="color: # - p));
/// &summary&
/// 根据指定的几率数组产生符合离散分布的随机数。
/// &/summary&
/// &param name="probabilities"&各取值的可能性。&/param&
/// &returns&符合随机分布的随机整数。&/returns&
public static double Discrete(double[] probabilities)
if (probabilities == null)
throw new ArgumentNullException("Argument array is null");
double EPSION = 1E-<span style="color: #;
double sum = <span style="color: #;
for (int i = <span style="color: #; i & probabilities.L i++)
if (probabilities[i] &= <span style="color: #)
throw new ArgumentException("array entry " + i + " must be nonnegative:" + probabilities[i]);
sum += probabilities[i];
if (sum & <span style="color: #.0 + EPSION || sum & <span style="color: #.0 - EPSION)
throw new ArgumentException("sum of array entries does not equal 1.0:" + sum);
while (true)
double r = UniformGenerator.NextDouble();
sum = <span style="color: #.0;
for (int i = <span style="color: #; i & probabilities.L i++)
sum += probabilities[i];
if (sum & r)
Main 方法：
namespace _2._1._35
* 不均匀的概率分布。编写一个测试用例，使用非均匀分布的概率来生成随机排列的数据，包括：
* 高斯分布
* 泊松分布
* 几何分布
* 离散分布（一种特殊情况见练习 2.1.28）。
* 评估并验证这些输入数据对本节讨论的算法的影响。
class Program
static void Main(string[] args)
InsertionSort insertionSort = new InsertionSort();
SelectionSort selectionSort = new SelectionSort();
ShellSort shellSort = new ShellSort();
int n = <span style="color: #000;
// 高斯分布（正态分布）
double[] arrayInsertion = SortCompare.GetNormalDistributionArray(n);
double[] arraySelection = new double[n];
double[] arrayShell = new double[n];
arrayInsertion.CopyTo(arraySelection, <span style="color: #);
arrayInsertion.CopyTo(arrayShell, <span style="color: #);
Console.WriteLine("Normal Distribution:");
Console.WriteLine("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, <span style="color: #);
arrayInsertion.CopyTo(arrayShell, <span style="color: #);
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, <span style="color: #.3);
arrayInsertion.CopyTo(arraySelection, <span style="color: #);
arrayInsertion.CopyTo(arrayShell, <span style="color: #);
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[] { <span style="color: #.1, <span style="color: #.2, <span style="color: #.3, <span style="color: #.1, <span style="color: #.1, <span style="color: #.1, <span style="color: #.1 });
arrayInsertion.CopyTo(arraySelection, <span style="color: #);
arrayInsertion.CopyTo(arrayShell, <span style="color: #);
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));
不均匀的数据。编写一个测试用例，生成不均匀的测试数据，包括：
一半数据是 0，一半数据是 1
一半数据是 0，1/4 是 1，1/4 是 2，以此类推
一半数据是 0，一半是随机 int 值。
评估并验证这些输入数据对本节讨论的算法的性能的影响。
最后结果：
namespace _2._1._36
* 不均匀的数据。
* 编写一个测试用例，
* 生成不均匀的测试数据，包括：
* 一半数据是 0，一半数据是 1
* 一半数据是 0，1/4 是 1，1/4 是 2，以此类推
* 一半数据是 0，一半是随机 int 值。
* 评估并验证这些输入数据对本节讨论的算法的性能的影响。
class Program
// 选择排序的耗时与输入值的内容无关，不受影响。
// 对于插入排序，以上几种情况都是重复值较多的情况，插入排序的速度会加快。
// 希尔排序本质上也是插入排序，因此也会更快一些。
static void Main(string[] args)
int n = <span style="color: #000;
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, <span style="color: #);
arrayInsertion.CopyTo(arrayShell, <span style="color: #);
Console.WriteLine("totally random");
Console.WriteLine("Insertion Sort:" + SortCompare.TimeRandomInput(insertionSort, n, <span style="color: #));
Console.WriteLine("Selection Sort:" + SortCompare.TimeRandomInput(selectionSort, n, <span style="color: #));
Console.WriteLine("Shell Sort:" + SortCompare.TimeRandomInput(shellSort, n, <span style="color: #));
Console.WriteLine();
// 一半是 0 一半是 1
arrayInsertion = HalfZeroHalfOne(n);
arrayInsertion.CopyTo(arraySelection, <span style="color: #);
arrayInsertion.CopyTo(arrayShell, <span style="color: #);
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, <span style="color: #);
arrayShell.CopyTo(arrayShell, <span style="color: #);
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, <span style="color: #);
arrayShell.CopyTo(arrayShell, <span style="color: #);
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:" + SortCo