数据结构综合排序实训.pdf

桂林航天工业学院 课 程 设 计 报 告 书 课 程 名：数据结构 题 目：排序综合 班 级：计算机应用技术 学 号：LZ502010118 姓 名：李 杭 4n 评语：成绩：指导教师：批阅时间：年 月 日 目录 一、实验目的.3 二、实验内容.3（1）至少采用三种方法实现上述问题求解.3（2）统计每一种排序方法的性能.3 三、实验说明（无）.3 四、实验步骤或算法描述.3（3）直接插入排序.3（4）二分查找.3（5）冒泡排序.4（6）直接选择排序.4 五、分析与思考（出现的问题）.4 六、测试数据与实验结果.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 一、实验目的一、实验目的 本实验通过实现直接插入排序、二分插入排序、冒泡排序和直接选择排序算法，使学生我理解如何实现排序算法思想。通过练习，加强对算法的理解，提高编程能力。二、实验内容二、实验内容 排序综合 利用随机函数产生 N 个随机整数（20000 以上），对这些数进行多种方法进行排序。要求：（1）至少采用三种方法实现上述问题求解至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（2）统计每一种排序方法的性能统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。三、实验说明（无）三、实验说明（无）四、四、实验步骤或算法描述实验步骤或算法描述 （3 3）直接插入排序直接插入排序：在排序过程中，每次都讲无序区中第一条记录插入到有序区中适当位置，使其仍保持有序。初始时，取第一条记录为有序区，其他记录为无序区。显然，随着排序过程的进行，有序区不断扩大，无序区不断缩小。最终无序区变为空，有序区中包含了所有的记录，排序结束。（4）二分查找二分查找：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前 4/18 一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。（5 5）冒泡排序冒泡排序：设想排序表 R1到 Rn垂直放置，将每个记录 Ri看作是重量为 Ri.key 的气泡；根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R，凡违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。（6 6）直接选择排序直接选择排序：第一次从 R0Rn-1中选取最小值，与 R0交换，第二次从 R1Rn-1中选取最小值，与 R1交换，.，第 i 次从 Ri-1Rn-1中选取最小值，与 Ri-1交换，.，第 n-1 次从 Rn-2Rn-1中选取最小值，与 Rn-2交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列 五、分析与思考（出现的问题）五、分析与思考（出现的问题）（1）已经采用四种方法直接插入排序、二分插入排序、冒泡排序和直接选择排序实现问题求解，（2）并把排序后的结果保存在不同的文件中。BinaryInsertSort.txt Bubblesort.txt insertsort.txt selectsort.txt（3）统计每一种排序方法的性能 找出其中两种较快的方法。六、测试数据与实验结果六、测试数据与实验结果 （1 1）算法流程图算法流程图：直接插入排序 5/18 开始Temp=RiRj+1=Rj;j-;i=0)&(tempRj)是否否 Rj+1=temp结束 二分插入排序 6/18 开始 intemp=Rileft=rightmiddle=(left+right)/2temp=leftRj+1=RjRleft=temp结束left=middle+1否否否是是是 冒泡排序 7/18 开始i=iRjRj-1t=Rj Rj=Rj-1 Rj-1=t;flag=1flag=0return结束否否否否是是是是 直接选择排序 8/18 开始in-1jnRjRmm=im=jm!=it=Ri Ri=RmRm=t 结束否否否否是是是是 9/18 打印 开始i=0;in;i+i%10=0nRin结束否否是是 主菜单 10/18 冒 泡 排 序二分插入排序直接选择排序返回直接插入排序打印随机数开始直接插入排序的时间是：t二分插入排序的时间为 t冒泡排序的时间为 t直接选择排序的时间为 t结束（2 2）输入数据截图：输入数据截图：11/18 （3 3）运行结果截图运行结果截图：12/18 13/18 七、实验心得与体会七、实验心得与体会 （1 1）插入冒泡排序）插入冒泡排序 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较 快的速度。反而在这种情况下，快速排序反而慢了。当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。宜用归并排序。当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。（2 2）插入排序、冒泡排序、选择排序的时间复杂性插入排序、冒泡排序、选择排序的时间复杂性 插入排序、冒泡排序、选择排序的时间复杂性为 O(n2)其它非线形排序的时间复杂性为 O(nlog2n)线形排序的时间复杂性为 O(n);（3 3）软件）软件影响影响 在算法运行期间，运行软件 会影响绝对时间和逻辑时间，使时间增大 （4 4）排序的）排序的数量数量 随着 n 的取值增大，算法的实际时间增长速度逐渐增大。（5 5）关键字比较）关键字比较 直接插入排序、冒泡排序（上升、下沉）、（递归、非递归）的关 键字比较次数相同，但绝对时间相差比较大；直接选择排序与冒泡排序的关键字比较次数相 近。（6 6）相比较其他的数据相比较其他的数据 相比较其他的数据，直接插入（有、无监视哨），直接选择，冒泡（上升、下 14/18 沉）的 结果相差较小，结果相差很大，另快速（递归），堆（递归，非递归），二路归并（非 递归）结果并不会受计算机环境而不同。八、八、附录（程序代码，含注释）附录（程序代码，含注释）（1 1）代码代码 /paixu.cpp:定义控制台应用程序的入口点。/*排序综合 利用随机函数产生 N 个随机整数（20000 以上），对这些数进行多种方法进行排序。要求：1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3)如果采用 4 种或 4 种以上的方法者，可适当加分。*/#include stdafx.h#include iostream#include stdio.h#include stdlib.h#include iomanip#include time.h using namespace std;FILE*fp1,*fp2,*fp3,*fp4;const int N=50000;#define ElemType int void insertsort(ElemType R,int n)/直接插入排序 fp1=fopen(insertsort.txt,w);for(int i=1;i=0)&(tempRj)15/18 Rj+1=Rj;j-;/顺序比较和移动 Rj+1=temp;fprintf(fp1,%dt,Ri);fclose(fp1);printf(t 已保存直接插入排序结果到 insertsort.txt 文件t);void BinaryInsertSort(ElemType R,int n)/二分插入排序 fp2=fopen(BinaryInsertSort.txt,w);for(int i=1;in;i+)/共进行 n-1 次插入 int left=0,right=i-1;ElemType temp=Ri;while(left=right)int middle=(left+right)/2;/取中点 if(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,w);int flag=1;/当 flag 为 0 则停止排序 for(int i=1;i=i;j-)if(RjRj-1)/发生逆序 ElemType t=Rj;Rj=Rj-1;Rj-1=t;flag=1;16/18 /fprintf(fp3,%dt,Ri);/交换，并标记发生了交换 if(flag=0)return;fclose(fp3);printf(t 已保存冒泡排序结果到 Bubblesort.txt 文件t);void selectsort(ElemType R,int n)/直接选择排序 fp4=fopen(selectsort.txt,w);int i,j,m;ElemType t;for(i=0;in-1;i+)m=i;for(j=i+1;jn;j+)if(RjRm)m=j;if(m!=i)t=Ri;Ri=Rm;Rm=t;fprintf(fp4,%dt,Ri);fclose(fp4);printf(t 已保存直接选择排序结果到 selectsort.txt 文件t);void print(ElemType R,int n)/打印数组 for(int i=0;in;i+)if(i%10=0)printf(n);printf(%7d,Ri);printf(n);double tt,tt1,tt2,tt3,tt4;void px()cout 找出其中两种较快的方法是 endl;if(tt1 tt2)if(tt1 tt3)cout 直接插入排序.t tt1 endl;else 17/18 if(tt3 tt4)cout 冒 泡 排 序.t tt3 endl;else cout 直接选择排序.t tt4 endl;else if(tt2 tt3)cout 直接插入排序.t tt2 endl;else if(tt3 tt4)cout 冒 泡 排 序.t tt3 endl;else cout 直接选择排序.t tt4 endl;void main()system(title 四种排序综合：李杭);int sele;ElemType RN,TN;int n,k;long t1,t2;srand(1);for(int i=0;iN;i+)Ti=rand();/产生 50000 个随机数 print(T,N);system(cls);printf(nnt 随机函数产生 50000 个随机整数nn);printf(tt 排序 子系统n);18/18 printf(tt*n);printf(tt*1-直接插入排序 *n);printf(tt*2-二分插入排序 *n);printf(tt*3-冒 泡 排 序 *n);printf(tt*4-直接选择排序 *n);printf(tt*0-返 回 *n);printf(tt*n);do printf(tt 请选择菜单项(04)：);scanf(%d,&k);for(int i=0;iN;i+)Ri=Ti;t1=time(NULL);switch(k)case 1:insertsort(R,N);t2=time(NULL);tt1=difftime(t2,t1);cout 直接插入排序的时间是：;cout tt1 endl;px();break;case 2:BinaryInsertSort(R,N);t2=time(NULL);tt2=difftime(t2,t1);cout 二分插入排序的时间为：tt2 endl;px();break;case 3:Bubblesort(R,N);t2=time(NULL);tt3=difftime(t2,t1);cout 冒泡排序的时间为：tt3 endl;px();break;case 4:selectsort(R,N);t2=time(NULL);tt4=difftime(t2,t1);cout 直接选择排序的时间为：tt4 endl;px();while(k);