实验五：排序方法的比较

《实验五：排序方法的比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、成绩：实验报告课程名称：数据结构实验实验项目：排序方法的比较姓名：李翠超专业：计算机科学与技术班级：计算机16-6学号：1609040307计算机科学与技术学院实验教学中心2017年12月20日哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告实验项目名称：排序方法的比较一、实验目的1.通过实验掌握排序的基本概念，掌握各种排序的基本思想和算法实现。2.能够较为灵活的选用某种排序方法解决问题二、实验内容1.实现常用的内部排序算法并进行比较：如起泡排序、直接插入排序、简单选择排序、快速排序等至少四种排序算法。试通过随机

2、数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。以实践教学，加深对教材内容的吸收，提升自己。2.冒泡排序的基本思想：通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。3.直接插入排序基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与

3、有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。4．快速排序的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。三、实验操作步骤1.阅读实验内容和要求 2.基本要求：待排序表的表长不小于100；至少要用5组不同的输入数据作测试；至少完成四个算法。    3.根据编译的结果，如果错误的及时找

4、出并改正四、实验结果分析哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告五、源代码#include#include#defineOK1#defineERROR0#defineMAX_LENGTH_INSERT_SORT7//用于快速排序时判断是否选用插入排序阙值#defineMAXSIZE10000//用于要排序数组个数最大值，可根据需要修改#defineMax20typedefstruct{intr[MAXSIZE+1];//用于存储要排序数组，r[0]用作哨兵或临时变量int

5、length;//用于记录顺序表的长度}SqList;//交换L中数组r的下标为i和j的值voidswap(SqList*L,inti,intj){inttemp=L->r[i];L->r[i]=L->r[j];L->r[j]=temp;}voidprint(SqListL){inti;for(i=1;i

6、i,j;哈尔滨理工大学计算机科学与技术学院实验教学中心实验报告for(i=1;ilength;i++){for(j=L->length-1;j>=i;j--){//注意j是从后往前循环{if(L->r[j]>L->r[j+1]){//若前者大于后者（注意这里与上一算法的差异）swap(L,j,j+1);//交换L->r[j]与L->r[j+1]的值}}}}//对顺序表L作简单选择排序voidSelectSort(SqList*L){inti,j,min;for(i=1;ilength;i++){min=

7、i;//将当前下标定义为最小值下标for(j=i+1;j<=L->length;j++){//循环之后的数据if(L->r[min]>L->r[j])//如果有小于当前最小值的关键字min=j;//将此关键字的下标赋值给min}if(i!=min)//若min不等于i，说明找到最小值，交换swap(L,i,min);//交换L->r[i]与L->r[min]的值}}//对顺序表L作直接插入排序voidInsertSort(SqList*L){inti,j;for(i=2;i<=L->length;i++){if(L->

8、r[i]r[i-1]){//需将L->r[i]插入有序子表L->r[0]=L->r[i];//设置哨兵for(j=i-1;L->r[j]>L->r[0];j--)L->r[j+1]=L->r[j];//记录后移L->r[j+1]=L->r[0];//插入到正确位置}}}//堆排序,已知L->r[s..m]中记录的关键字除L