《数据结构综合排序实训》由会员分享，可在线阅读，更多相关《数据结构综合排序实训（18页珍藏版）》请在金锄头文库上搜索。
1、桂林航天工业学院 课程设计报告书 课 程 名 ： 数据结构 题 目： 排序综合 班 级： 计算机应用技术 学 号： LZ502010118 姓 名： 李 杭 4n 评语： 成绩： 指导教师： 批阅时间： 年 月 日 目录 一、实验目的 . 3 二、实验内容 . 3 （ 1） 至少采用三种方法实现上述问题求解 . 3 （ 2） 统计每一种排序方法的性能 . 3 三、实验说明（无） . 3 四、实验步骤或算法描述 . 3 （ 3） 直接插入排序 . 3 （ 4） 二分查找 . 3 （ 5） 冒泡排序 . 4 （ 6） 直接选择排序 . 4 五、分析与思考（出现的问题） . 4 六、测试数据与实验结
2、果 . 4 （ 1）算法流程图： . 4 （ 2）输入数据截图： . 10 （ 3）运行结果截图： . 11 七、实验心得与体会 . 13 （ 1）插入冒泡排序 . 13 （ 2）插入排序、冒泡排序、选择排序的时间复杂性 . 13 （ 3）软件影响 . 13 （ 4）排序的数量 . 13 （ 5）关键字比较 . 13 （ 6）相比较其他的数据 . 13 八、附录（程序代码，含注释） . 14 （ 1） 代码 . 14 3 / 18 一、实验目的 本实验通过实现 直接插入排序、二分插入排序、冒泡排序和直接选择排序 算法，使学生 我理解如何实现 排序算法思想。通过练习，加强对算法的理解，提高编程能
3、力。 二、实验内容 排序综合 利用随机函数产生 N 个随机整数（ 20000 以上），对这些数进行多种方法进行排序。 要求： （ 1） 至少采用三种方法实现上述问题求解 （提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 （ 2） 统计每一种排序方法的性能 （以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 三、实验说明（无） 四、 实验步骤或算法描述 （ 3） 直接插入排序 ：在排序过程中，每次都讲无序区中第一条记录插入到有序区中适当位置，使其仍保持有序。初始时，取第一条记录为有序区，其他记录为无
4、序区。显然，随着排序过程的进行，有序区不断扩大，无序区不断缩小。最终无序区变为空，有序区 中包含了所有的记录，排序结束。 （ 4） 二分查找 ： 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前 4 / 18 一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找
5、成功，或直到子表不存在为止，此 时查找不成功。 （ 5） 冒泡排序 ：设想排序表 R1到 Rn垂直放置，将每个记录 Ri看作是重量为 Ri.key 的气泡；根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R，凡违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 （ 6） 直接选择排序 ： 第一次从 R0Rn-1中选取最小值，与 R0交换，第二次从 R1Rn-1中选取最小值，与 R1交换， .，第 i次从 Ri-1Rn-1中选取最小值，与 Ri-1交换， .，第 n-1次 从 Rn-2Rn-1中选取最小值，与 Rn-2交换，总共通过 n-1
6、次，得到一个按排序码从小到大排列的有序序列 五、分析与思考（出现的问题） （ 1） 已经采用四种方法 直接插入排序、二分插入排序、冒泡排序和直接选择排序 实现问题求解， （ 2） 并把排序后的结果保存在不同的文件中。 BinaryInsertSort.txt Bubblesort.txt insertsort.txt selectsort.txt （ 3） 统计每一种排序方法的性能 找出其中两种较快的方法。 六、测试数据与实验结果 （ 1） 算法流程图 ： 直接插入排序 5 / 18 开始Temp=RiRj+1= Rj; j- ;i=0)&(temp = l e f tR j + 1 = R j R l e f t = t e m p结束l e f t = m i d d l e + 1否否否是是是冒泡排序 7 / 18 开始i=iRj= 0) & (temp= left; j-) Rj + 1 = Rj; /元素后移空出插入位 Rleft = temp; fprintf(fp2, %dt, Ri); fclose(fp2); printf(t已保存二分插入排序结果到 BinaryInsertSort.txt 文件 t); void Bubblesort(ElemType R, int n) /冒泡排序 fp3 = fopen(Bubblesort.txt,
