第10次实验-实验报告

北京理工大学珠海学院实验报告

ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY

班级 学号 姓名 指导教师 成绩

实验题目 排序算法的实现 实验时间

一、实验目的、意义

（1）掌握排序的基本概念，对排序的稳定性及排序的时间复杂度有深刻的认识 （2）掌握Shell排序的的基本思想和算法实现 （3）掌握快速排序的基本思想和算法实现

（4）掌握选择排序中堆排序的基本思想和算法实现 （5）了解归并排序算法的基本思想和程序实现

二、实验内容及要求

说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。 具体要求：

本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序，在上述内容的基础上，将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路，新算法。

1.考虑对20个整数的随机输入进行排序，各排序功能基本上都可以成为独立调用的模块，因此可以先写出排序算法，然后用主函数调用。

三、实验所涉及的知识点

本实验涉及各类排序算法。

Shell排序：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量重复上述分组和排序，直至所取的增量dt=1(dt快速排序是对冒泡法的改进，其基本思想是：通过一趟排序将待排文件分割成独立的两部分，其中一部分记录的关键字值均比另一部分记录的关键字小，然后分别对这两部分进行排序，以达到整个序列有序。

四、实验记录

(调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。)

1

五、实验结果及分析

（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。）

六、总结与体会

（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。）

七、程序清单(包含注释)

2