《数据结构课程设计实验报告内部排序算法比较》由会员分享，可在线阅读，更多相关《数据结构课程设计实验报告内部排序算法比较（28页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计实验报告内部排序算法比较08级计算机科学与技术专业E10814131郭磊2010年06月13日【实验简介】1、 在教科书各种内部排序算法的时间复杂度分析结果只给出了算法执行的时间的阶，或大概的执行时间，如：直接插入排序即时间复杂度为O（n*n）2、 通过五组随机数据、一组正序数据与一组逆序数据比较6种常用的内部算法（起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序）的关键字比较次数和关键字移动次数，以取得直观感受；3、 用五组不同的长度不小于100的数据进行测试，并对测试结果作出简单的分析，对得出结果拨动大小的进行解释；【设计模块】调用调用调用HeapAdj
2、ust主函数生成随机数Switch函数菜单函数SelectSortinsertSortBubbleSortShellSortHeapSortserchSortQSort根据菜单函数返回值调用相应的操作函数【对应模块算法说明】(1) 此算法程序中需要用到顺序表数据类型,数据元素的类型定义如下:typedef structKeyType key; /关键字项RedType;typedef structRedType rMAXSIZE+1; /0号单元闲置或用作哨兵单元int length; /顺序表长度int info; /记录关键字移动次数int cmp; /关键字的比较次数Sqlist;(2)
3、 本实验用到六种排序算法，一个主函数和菜单函数,其中排序算法分别为起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序；相应时间复杂度分析如下：起泡排序：若待排序列为“正序”，则需进行一趟排序在排序过程中关键字需进行n-1次比较，无须移动纪录；若是“逆序”，则进行n-1趟排序，需n(n-1)/2次比较，并坐等数量级的移动，因此总的事件复杂度为O（n2）;直接插入排序 待排序纪录是随机的，关键字间的移动次数和比较次数的平均值约为n*n/4,即时间复杂度为O（n2）;简单的选择排序 虽然在排序过程中所需要的移动次数较少，最小时为0，最大时为3（n-1）；但是关键字的比较次数总是相同
4、的，均为n(n-1)/2，因此，时间复杂度亦为O（n2）;快速排序 其平均时间是kn*n,其中n为待排序列中纪录的个数，k为某个常数，其时间复杂度为O（n*n）；希尔排序 当增序序列为dltak=2t-k+1-1时，时间复杂度为O（n3/2）,其中t为排序趟数，1kt2(n+1);堆排序 此排序对于含n个元素的序列排序时，总共进行的关键字比较次数不超过4n，且在最坏的情况下，其时间复杂度为O（n*n）；算法分析如下： 冒泡排序 该算法的的思路是首先将第1个记录的关键字负值给L.r0，然后用L.r0与第（i+1）个记录的关键字比较,若为逆序,则交换第i与第i+1两记录的位置,然后让i加1，重复以
5、上操作，直至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-rj+1; /保证L-r0始终为较大的记录L-rj+1=L-r0; /把最大的记录放到祠堂排序的最高位置printf(L-rMAXSI
6、ZE);/输出排序后数组和相关数据直接插入排序 本算法的思路是，把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-2;(L-r0.key rj.key);j-)L-rj+1 = L-rj; /纪录后移L-rj+1 = L-r0; /插入到正确位置printf(L
7、-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.L.length中选key最小的if(L-r0.keyL-rk.key) L-r0=L-rk; j=k; if (i!=j) L.riL.rj; /与第i个记录交换
8、 printf(L-rMAXSIZE);/输出排序后数组和相关数据快速查找排序 其基本思想为，通过一趟排序将带排序记录分割成两部分，其中一部分记录的关键字均小于另一部分的关键字，再利用递归分别对分割所得到的子序列进行快速排序。其中一趟快速排序的算法为：int serchSort(Sqlist *L,int low,int high) /快速排序单次排序pivotkey=L-rlow.key; /枢轴纪录关键字while(lowhigh) while(lowrhigh.key=pivotkey) high-;L-rlow L-rhigh; /将比枢轴纪录小的纪录移到底端while(lowrlow
9、.keyrhigh L-rlow; /将比枢轴纪录大的纪录移到高端return high; /返回枢轴所在位置递归算法为：void QSort(Sqlist *L, int low, int high) / 快速排序 if (low high) / 长度大于1 pivotloc = serchSort(L, low, high); /调用serchSort（）将L.rlow.high一分为二 QSort(L, low, pivotloc-1); /对低子表递归排序，pivotloc是枢轴位置 QSort(L, pivotloc+1, high); / 对高子表递归排序 希尔排序 基本思路是先将
10、整个待排序的记录分割成若干个子序列进行直接排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次全体直接插入排序void ShellSort(Sqlist *L,int dlta,int t) /希尔排序for(k=1;k=t;k+)dltak=(int)pow( 2, t-k+1 )-1;/double pow( double base, double exp );函数返回以参数base 为底的exp 次幂for(i=dltak+1;ilength;i+)if(L-ri.key ri-dltak.key)L-r0 = L-ri;for(j=i-dltak;j0 & (L-r0.key
11、rj.key);j-=dltak)L-rj+dltak = L-rj;L-rj+dltak = L-r0;printf(L-rMAXSIZE);/输出排序后数组和相关数据堆排序 基本思想是使记录序列按关键字非递减有序排列，则再对排序的算法中先建立一个“大顶堆”，即先选得一个关键字为最大的记录与序列中最后一个记录交换，然后再对序列中前n-1记录进行筛选，重新将它调整为“大顶堆“，如此反复直至排序结束。void HeapAdjust(Sqlist *L, int s, int m) / 已知L.rs.m中记录的关键字除L.rs.key之外均满足堆的定义，本函数调整L.rs的关键字，使L.rs.m成
12、为一个大顶堆（对其中记录的关键字而言） rc = L-rs; for (j=2*s; j=m; j*=2) / 沿key较大的孩子结点向下筛选 if (jrj.keyrj+1.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 重新调整为大顶堆printf(L-rMAXSIZE);/输出排序后数组和相关数据菜单程序 利用do while 循环实现对菜单的正确选择，并返回选择的操作代码int menu_select() /
