数据结构课程设计实验报告-内部排序算法比较

《数据结构课程设计实验报告-内部排序算法比较》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构课程设计实验报告内部排序算法比较08级计算机科学与技术专业E郭磊2010年06月13日【实验简介】1、在教科书各种内部排序算法的时间复杂度分析结果只给出了算法执行的时间的阶，或大概的执行时间，如：直接插入排序即时间复杂度为O（n*n）2、通过五组随机数据、一组正序数据与一组逆序数据比较6种常用的内部算法（起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序）的关键字比较次数和关键字移动次数，以取得直观感受；3、用五组不同的长度不小于100的数据进行测试，并对测试结果作出简单的分析，对得出结果拨动大小的进行解释；【设计模块】调用调用调用HeapAdjust主函数生成随机数

2、Switch函数菜单函数SelectSortinsertSortBubbleSortShellSortHeapSortserchSortQSort根据菜单函数返回值调用相应的操作函数【对应模块算法说明】(1)此算法程序中需要用到顺序表数据类型,数据元素的类型定义如下:typedefstruct{KeyTypekey;//关键字项}RedType;typedefstruct{RedTyper[MAXSIZE+1];//0号单元闲置或用作哨兵单元intlength;//顺序表长度intinfo;//记录关键字移动次数intcmp;//关键字的比较次数}Sqlist;(2)本实验用到六种排序算法，一

3、个主函数和菜单函数,其中排序算法分别为起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序；相应时间复杂度分析如下：起泡排序：若待排序列为“正序”，则需进行一趟排序在排序过程中关键字需进行n-1次比较，无须移动纪录；若是“逆序”，则进行n-1趟排序，需n(n-1)/2次比较，并坐等数量级的移动，因此总的事件复杂度为O（n2）;直接插入排序待排序纪录是随机的，关键字间的移动次数和比较次数的平均值约为n*n/4,即时间复杂度为O（n2）;简单的选择排序虽然在排序过程中所需要的移动次数较少，最小时为0，最大时为3（n-1）；但是关键字的比较次数总是相同的，均为n(n-1)/2，因此，

4、时间复杂度亦为O（n2）;快速排序其平均时间是kn*㏑n,其中n为待排序列中纪录的个数，k为某个常数，其时间复杂度为O（n*㏑n）；希尔排序当增序序列为dlta[k]=2t-k+1-1时，时间复杂度为O（n3/2）,其中t为排序趟数，1≤k≤t≤㏒2(n+1);堆排序此排序对于含n个元素的序列排序时，总共进行的关键字比较次数不超过4n，且在最坏的情况下，其时间复杂度为O（n*㏑n）；算法分析如下：①冒泡排序该算法的的思路是首先将第1个记录的关键字负值给L.r[0]，然后用L.r[0]与第（i+1）个记录的关键字比较,若为逆序,则交换第i与第i+1两记录的位置,然后让i加1，重复以上操作，直至i

5、=n-1为止;依次进行第二趟、第三趟……作同样的操作，直至所有的记录按正序排列（一般需要n-1趟比较，第i趟从L.r[1]到L.r[n-i+1]依次比较，1≦i≦n-i，比较结果是让其中最大的记录放在L.r[n-i+1]的位置）voidBubbleSort(Sqlist*L)//冒泡排序{for(i=0;ilength;i++){L->r[0]=L->r[1];for(j=1;jr[0].key>=L->r[j+1].key)L->r[j]óL->r[j+1];//交换两记录的位置elseL->r[0]=L->r[j+1];//保证L->r[0]始终为较大

6、的记录L->r[j+1]=L->r[0];//把最大的记录放到祠堂排序的最高位置}printf(L->r[MAXSIZE]);//输出排序后数组和相关数据}②直接插入排序本算法的思路是，把L->r[0]设置为哨兵，排序时把第i个记录复制给哨兵，并于其前的i-1个记录进行比较，找到第一个比起大的记录，利用循环让记录后移，把其放到第一个比起大的记录前面。voidinsertSort(Sqlist*L)//直接插入排序{for(i=2;i<=L->length;i++){if((L->r[i].keyr[i-1].key)){L->r[0]=L->r[i];//复制哨兵L->r[i]=L->

7、r[i-1];for(j=i-2;(L->r[0].keyr[j].key);j--)L->r[j+1]=L->r[j];//纪录后移L->r[j+1]=L->r[0];//插入到正确位置}}printf(L->r[MAXSIZE]);//输出排序后数组和相关数据}③简单选择排序基本思想是在第i趟选择排序时：通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（