《数据结构课程设计报告---内部排序算法比较》由会员分享，可在线阅读，更多相关《数据结构课程设计报告---内部排序算法比较（28页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计实验报告内部排序算法比较08 级计算机科学与技术专业E108141312010 年 06 月 13 日【实验简介】1、 在教科书各种内部排序算法的时间复杂度分析结果只给出了算法执行的时间的阶，或大概的执行时间，如：直接插入排序即时间复杂度为O（n*n）2、 通过五组随机数据、一组正序数据与一组逆序数据比较 6 种常用的内部算法（起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序）的关键字比较次数和关键字移动次数，以取得直观感受；3、 用五组不同的长度不小于 100 的数据进行测试，并对测试结果作出简单的分析，对得出结果拨动大小的进行解释；【设计模块】调用调用调
2、用HeapAdjust主函数生成随机数 Switch 函数 菜单函数SelectSortinsertSortBubbleSort ShellSort HeapSortserchSortQSort根据菜单函数返回值调用相应的操作函数【对应模块算法说明】(1) 此算法程序中需要用到顺序表数据类型,数据元素的类型定义如下:typedef structKeyType key; /关键字项RedType;typedef structRedType rMAXSIZE+1; /0 号单元闲置或用作哨兵单元int length; /顺序表长度int info; /记录关键字移动次数int cmp; /关键字的
3、比较次数Sqlist;(2) 本实验用到六种排序算法，一个主函数和菜单函数,其中排序算法分别为起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序；相应时间复杂度分析如下：起泡排序：若待排序列为“正序” ，则需进行一趟排序在排序过程中关键字需进行 n-1 次比较，无须移动纪录；若是“逆序” ，则进行 n-1 趟排序，需 n(n-1)/2 次比较，并坐等数量级的移动，因此总的事件复杂度为 O（n 2）;直接插入排序 待排序纪录是随机的，关键字间的移动次数和比较次数的平均值约为n*n/4,即时间复杂度为 O（n 2）;简单的选择排序 虽然在排序过程中所需要的移动次数较少，最小时为
4、0，最大时为 3（n-1） ；但是关键字的比较次数总是相同的，均为 n(n-1)/2，因此，时间复杂度亦为 O（n 2）;快速排序 其平均时间是 kn*n,其中 n 为待排序列中纪录的个数，k 为某个常数，其时间复杂度为 O（n*n） ；希尔排序 当增序序列为 dltak=2t-k+1-1时，时间复杂度为 O（n 3/2）,其中 t 为排序趟数，1kt 2(n+1);堆排序 此排序对于含 n 个元素的序列排序时，总共进行的关键字比较次数不超过 4n，且在最坏的情况下，其时间复杂度为 O（n*n） ；算法分析如下： 冒泡排序 该算法的的思路是首先将第 1 个记录的关键字负值给 L.r0，然后用L
5、.r0与第（i+1）个记录的关键字比较,若为逆序,则交换第 i 与第 i+1 两记录的位置,然后让 i 加 1，重复以上操作，直至 i=n-1 为止;依次进行第二趟、第三趟作同样的操作，直至所有的记录按正序排列（一般需要 n-1 趟比较，第 i 趟从 L.r1到 L.rn-i+1依次比较，1 i n-i，比较结果是让其中最大的记录放在 L.rn-i+1的位置）void BubbleSort(Sqlist *L) /冒泡排序for(i=0;ilength;i+)L-r0=L-r1;for(j=1;jr0.key=L-rj+1.key)L-rjL-rj+1; /交换两记录的位置elseL-r0=L
6、-rj+1; /保证 L-r0始终为较大的记录L-rj+1=L-r0; /把最大的记录放到祠堂排序的最高位置printf(L-rMAXSIZE);/输出排序后数组和相关数据直接插入排序 本算法的思路是，把 L-r0设置为哨兵，排序时把第 i 个记录复制给哨兵，并于其前的 i-1 个记录进行比较，找到第一个比起大的记录，利用循环让记录后移，把其放到第一个比起大的记录前面。void insertSort(Sqlist *L) /直接插入排序for(i=2;ilength;i+)if(L-ri.key ri-1.key)L-r0 = L-ri; /复制哨兵L-ri = L-ri-1;for(j=i-
7、2;(L-r0.key rj.key);j-)L-rj+1 = L-rj; /纪录后移L-rj+1 = L-r0; /插入到正确位置printf(L-rMAXSIZE);/输出排序后数组和相关数据简单选择排序 基本思想是在第 i 趟选择排序时：通过 n-i 次关键字之间的比较，从n-i+1 个记录中选出关键字最小的记录，并和第 i（1 i n）个记录交换之void SelectSort(Sqlist *L) / 简单选择排序 for (i=1; ilength; +i) / 选择第 i 小的记录，并交换到位 L-r0=L-ri;j=i;for(k=i+1;klength;k+)/从 L.ri.
8、L.length中选 key 最小的if(L-r0.keyL-rk.key)L-r0=L-rk;j=k;if (i!=j) L.riL.rj; /与第 i 个记录交换printf(L-rMAXSIZE);/输出排序后数组和相关数据快速查找排序 其基本思想为，通过一趟排序将带排序记录分割成两部分，其中一部分记录的关键字均小于另一部分的关键字，再利用递归分别对分割所得到的子序列进行快速排序。其中一趟快速排序的算法为：int serchSort(Sqlist *L,int low,int high) /快速排序单次排序pivotkey=L-rlow.key; /枢轴纪录关键字while(lowrhi
9、gh.key=pivotkey) high-;L-rlow L-rhigh; /将比枢轴纪录小的纪录移到底端while(lowrlow.keyrhigh L-rlow; /将比枢轴纪录大的纪录移到高端return high; /返回枢轴所在位置递归算法为：void QSort(Sqlist *L, int low, int high) / 快速排序 if (low length;i+)if(L-ri.key ri-dltak.key)L-r0 = L-ri;for(j=i-dltak;j0 j-=dltak)L-rj+dltak = L-rj;L-rj+dltak = L-r0;printf(
10、L-rMAXSIZE);/输出排序后数组和相关数据堆排序 基本思想是使记录序列按关键字非递减有序排列，则再对排序的算法中先建立一个“大顶堆” ，即先选得一个关键字为最大的记录与序列中最后一个记录交换，然后再对序列中前 n-1 记录进行筛选，重新将它调整为“大顶堆“，如此反复直至排序结束。void HeapAdjust(Sqlist *L, int s, int m) / 已知 L.rs.m中记录的关键字除L.rs.key 之外均满足堆的定义，本函数调整 L.rs的关键字，使 L.rs.m成为一个大顶堆（对其中记录的关键字而言）rc = L-rs;for (j=2*s; jrj.keyrj+1.
11、key) +j;/j 为 key 较大记录的下标if (rc.key = L-rj.key) break; / rc 应插入在位置 s 上L-rs = L-rj; s = j;L-rs = rc; / 插入void HeapSort(Sqlist *L) /堆排序for(i=L-length/2;i0;i-) /把 H-r建成大顶堆HeapAdjust ( L, i, L-length );for(i=L-length;i1;i-)L-ri L-r1; /将堆顶记录和当前未经排序子序列 L.r1i中/最后一个记录相互交换HeapAdjust(L, 1, i-1); / 将 H.r1.i-1 重
12、新调整为大顶堆printf(L-rMAXSIZE);/输出排序后数组和相关数据菜单程序 利用 do while 循环实现对菜单的正确选择，并返回选择的操作代码int menu_select() /菜单目录int nu;char s;printf(*n);printf(*菜单*n);printf(1.BubbleSortn); /冒泡排序printf(2.insertSortn); /直接插入排序printf(3.SelectSortn); / 简单选择排序printf(4.QSortn); /查找排序printf(5.ShellSortn); /希尔排序printf(6.HeapSortn);
13、 /堆排序printf(7.退出程序n);printf(*n);printf(请输入数字：1-7 选择相应的排序方式或操作：n);dos=getchar();nu=(int)s-48;while(nu55);return (nu);主函数 是程序的入口，包括两个 for 循环，一个用来实现随机数产生与输出；另一个用来实现菜单的选择的连续；第二个 for 循环中包含一个 switch 循环，作用是根据菜单程序的返回值选择相应的操作，随后作相应的修改使待排序数据分别为正序和逆序，以实现本设计的目的。void main()printf(输出待排序的数据:);for(;)switch(menu_sel
14、ect() /选择相应的排序操作case 1: BubbleSort(case 2: insertSort(case 3: SelectSort(case 4: QSort(case 5: ShellSort(case 6: HeapSort(case 7: exit(0);运行结果：第一组随机数据及其运行结果如下：第二组随机数据及其运行结果如下：第三组随机数据及其运行结果如下：第四组随机数据及其运行结果如下：第五组随机数据及其运行结果如下：第六组正序数据及其运行结果如下： 第七组逆序数据及其运行结果如下： 【小结与讨论】表中数据为关键字移动次数：BubbleSort insertSort SelectSort QSort ShellSort HeapSort第一组 6974 2690 605
