希尔排序问题实验报告

希尔排序问题

摘要：voidShellInsert 为希尔排序函数，主要功能为实现对数的排序，srand为系统中的随机函数，需要根据输入的种子值，得出最终的随机数。

关键词：SqList,voidShellInsert,seed,srand,dk

1. 问题分析

利用随机函数产生N 个随机整数（10个以上），对这些数进行从小到大的排序，此外至少采用3次缩小增量。

2.

概要设计

3.详细设计

首先是对于随机函数的程序编写，要产生10个以上的随机数，要求用户通过键入所需随机数的个数来控制所求的随机数数量，并且同时将所得的随机数记录到数组r 中.

其次要求用希尔排序的算法对于无序的随机数进行从小到大的排列，并且要求采用至少3次缩小增量，用户可以根据自身的需要对于缩小增量进行定义并键入，然后通过调用希尔排序函数实现最终的排序功能.主要代码如下：

最终通过输出语句，显示每趟经过希尔排序得出的结果。

4.调试分析

图4_1

随机函数产生随机数

图4_2根据用户的需求输入缩小增量

图4_3根据输入的缩小增量对于无序随机数进行希尔排序

5.课程实验小结

关于希尔排序，最关键的是深刻了解每一趟的排序过程，希尔排序又称“缩小增量排序”，它也是一种属插入排序类的方法，但在时间效率上较其他几种排序方法有较大的改进。希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序的一个特点是：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。

虽然本次课程实验中，增量序列可以有各种取法，但需注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1.

参考文献：

[1]严蔚敏，吴伟民. 《数据结构（C 语言版）》. 清华大学出版社，1997,4：264,271-272.

[2]李含光，郑关胜. 《C 语言程序设计教程》. 清华大学出版社，20011,1:108-114.

[3]《C 语言随机函数》.

http://baike.baidu.com/link?url=2pddDvMYHRHH9qVl0-CHnvY1KfENbdLcPuMRqSTpxDMJ8z1-GqZ-CNkSlTXGkZKT.2013年12月25日访问

[4]《希尔排序》

http://baike.baidu.com/link?url=rs0a3W-teVl45ijex-9SbsOJcIrjTbC5y8ETUkxfiTtUAAuwg36-cCRsWIwpM5I5.2013年12月26日访问

[5]《希尔排序法》.

http://baike.baidu.com/link?url=xf3XOyxgBTlS36sk1x4RVbukAAf2MtJMBEga7VGCZ-V0gl_AKM9EyAPXnZ5LsQ4TLFolT-Tsmf44QQ6YTcU2z_.2013年12月26日访问