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

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;

13、i-)l-ri l-r1; /将堆顶记录和当前未经排序子序列l.r1i中/最后一个记录相互交换heapadjust(l, 1, i-1); / 将h.r1.i-1 重新调整为大顶堆printf(l-rmaxsize);/输出排序后数组和相关数据菜单程序 利用do while 循环实现对菜单的正确选择，并返回选择的操作代码int menu_select() /菜单目录int nu;char s;printf(*n);printf(*菜单*n);printf(1.bubblesortn); /冒泡排序printf(2.insertsortn); /直接插入排序printf(3.selectsort

14、n); / 简单选择排序printf(4.qsortn); /查找排序printf(5.shellsortn); /希尔排序printf(6.heapsortn); /堆排序printf(7.退出程序n);printf(*n);printf(请输入数字：1-7 选择相应的排序方式或操作：n); dos=getchar();nu=(int)s-48;while(nu55);return (nu);主函数 是程序的入口，包括两个for循环，一个用来实现随机数产生与输出；另一个用来实现菜单的选择的连续；第二个for循环中包含一个switch循环，作用是根据菜单程序的返回值选择相应的操作，随后作相应的

15、修改使待排序数据分别为正序和逆序，以实现本设计的目的。void main() printf(输出待排序的数据:);for(;)switch(menu_select() /选择相应的排序操作case 1: bubblesort(&a);break;case 2: insertsort(&b);break;case 3: selectsort(&c);break;case 4:qsort(&l,1,l.length); break;case 5: shellsort(&d,dlta,t);break;case 6: heapsort(&e);break;case 7: exit(0);运行结果：第

16、一组随机数据及其运行结果如下：第二组随机数据及其运行结果如下：第三组随机数据及其运行结果如下：第四组随机数据及其运行结果如下：第五组随机数据及其运行结果如下：第六组正序数据及其运行结果如下： 第七组逆序数据及其运行结果如下： 【小结与讨论】表中数据为关键字移动次数：bubblesortinsertsortselectsortqsortshellsortheapsort第一组697426906053937231082第二组706624735863827421081第三组707227335924087241075第四组706825875833687881087第五组6963278762040275

17、41085第六组99000029701136第七组4950514826502975401012下表中数据为关键字比较次数：bubblesortinsertsortselectsortqsortshellsortheapsort第一组495025044950638785749第二组495022934950635790752第三组495025504950600796752第四组495024044950625824748第五组495026074950621804745第六组49509949504950480811第七组4950495049504950672662有数据分析可知：无论待排序列排序如何，

18、bubblesort与selectsort两种算法的关键字比较次数均为4950，即n(n-1)/2次；待排序列为随机序列时直接插入排序的关键字比较次数和关键字移动平均值约为n2/4,正序时比较次数为(n-1),移动次数为0，逆序时为n(n-1)/2次；整体看来六种排序中qsort、shellsort 、heapsort三种排序比较和移动次数相对较少；但bubblesort、 insertsort两种排序属于稳定性排序（每交换一次纪录，关键字就有三次移动纪录）。在测试过程中，当连续选择一个操作时，发现有的排序方式的关键字移动次数会随之增加，例如bubblesort，qsort，heapsort；

19、仔细分析后得知，无论待排序列是否排好，它每次运行都会有关键字的移动；每次运行程序，六种排序方式的关键字比较次数也会随着操作次数的增加而增加，原因与上一个问题先同。【程序清单】#include#include#include#include #include#define maxsize 100typedef int keytype; /定义关键字的整数类型typedef structkeytype key; /关键字项redtype;typedef structredtype rmaxsize+1; /0号单元闲置或用作哨兵单元int length; /顺序表长度int info; /记录关键

20、字移动次数int cmp; /关键字的比较次数sqlist;/*/void bubblesort(sqlist *l) /冒泡排序int i,j;int n=l-length;for(i=0;ilength;i+)l-r0=l-r1;for(j=1;jr0.key=l-rj+1.key)l-rj=l-rj+1;l-info+;elsel-rj=l-r0;l-r0=l-rj+1;l-info+=2;l-cmp+;l-rj+1=l-r0;printf(以下数据的排列顺序为bubblesort排序后的排列顺序：n);for(i=1;iri);/输出排序后数组和相关数据printf(关键字移动次数为：

21、%dn,l-info);printf(关键字比较次数为：%dn,l-cmp);/*/void insertsort(sqlist *l) /直接插入排序int i,j;for(i=2;ilength;i+)l-cmp+;if(l-ri.key ri-1.key)l-r0 = l-ri; /复制哨兵l-ri = l-ri-1;l-info+=2;for(j=i-2;(l-r0.key rj.key);j-)l-rj+1 = l-rj; /纪录后移l-info+;l-cmp+;l-rj+1 = l-r0; /插入到正确位置l-info+;printf(以下数据的排列顺序为insertsort排序后

22、的排列顺序：n);for(i=1;ilength;i+)printf(%dt,l-ri);/输出排序后数组和相关数据printf(关键字移动次数为：%dn,l-info);printf(关键字比较次数为：%dn,l-cmp);/*/void selectsort(sqlist *l) / 简单选择排序 int i,j,k; for (i=1; ilength; +i) / 选择第i小的记录，并交换到位 l-r0=l-ri;j=i; for(k=i+1;klength;k+) / 在l.ri.l.length中选key最小者 l-cmp+; if(l-r0.keyl-rk.key) l-r0=l

23、-rk; j=k; l-info+; if (i!=j) / l.ril.rj; 与第i个记录交换 redtype temp; temp=l-ri; l-ri=l-rj; l-rj=temp; l-info+=3; printf(以下数据的排列顺序为selectsort排序后的排列顺序：n);for(i=1;ilength;i+)printf(%dt,l-ri);/输出排序后数组和相关数据printf(关键字移动次数为：%dn,l-info);printf(关键字比较次数为：%dn,l-cmp);/*/int serchsort(sqlist *l,int low,int high) /查找排

24、序单次排序int pivotkey;l-r0 = l-rlow;pivotkey=l-rlow.key; /枢轴纪录关键字while(lowhigh) while(lowrhigh.key=pivotkey)high-;l-cmp+;l-rlow = l-rhigh; /将比枢轴纪录小的纪录移到底端l-info+;while(lowrlow.keycmp+;l-rhigh = l-rlow; /将比枢轴纪录大的纪录移到高端l-info+;l-rlow = l-r0;l-info+;return high;void qsort(sqlist *l, int low, int high) / 快速

25、排序 int pivotloc; if (low high) / 长度大于1 pivotloc = serchsort(l, low, high); / 将l.rlow.high一分为二 qsort(l, low, pivotloc-1); / 对低子表递归排序，pivotloc是枢轴位置 qsort(l, pivotloc+1, high); / 对高子表递归排序 /*/void shellsort(sqlist *l,int dlta,int t) /希尔排序int i,k,j;for(k=1;k=t;k+)dltak=(int)pow( 2, t-k+1 )-1;/double pow(

26、 double base, double exp );函数返回以参数base 为底的exp 次幂for(i=dltak+1;ilength;i+)l-cmp+;if(l-ri.key ri-dltak.key)l-r0 = l-ri;l-info+;for(j=i-dltak;j0 & (l-r0.keyrj.key);j-=dltak)l-cmp+;l-rj+dltak = l-rj;l-info+;l-rj+dltak = l-r0;l-info+;printf(以下数据的排列顺序为shellsort排序后的排列顺序：n);for(i=1;ilength;i+)printf(%dt,l-r

27、i);/输出排序后数组和相关数据printf(关键字移动次数为：%dn,l-info);printf(关键字比较次数为：%dn,l-cmp);/*/void heapadjust(sqlist *l, int s, int m) / 已知l.rs.m中记录的关键字除l.rs.key之外均满足堆的定义，本函数调整l.rs的关键字，使l.rs.m成为一个大顶堆（对其中记录的关键字而言） int j; redtype rc; rc = l-rs; l-info+; for (j=2*s; jcmp+; if (jrj.keyrj+1.key) +j; / j为key较大的记录的下标 l-cmp+;

28、if (rc.key = l-rj.key) break; / rc应插入在位置s上 l-rs = l-rj; l-info+; s = j; l-rs = rc; / 插入 l-info+;void heapsort(sqlist *l) /堆排序int i;redtype rc;for(i=l-length/2;i0;i-) /把h-r建成大顶堆 heapadjust ( l, i, l-length );for(i=l-length;i1;i-)rc = l-ri;l-ri = l-r1;l-r1 = rc;l-info+=3;heapadjust(l, 1, i-1); / 将h.r1

29、.i-1 重新调整为大顶堆printf(以下数据的排列顺序为heapsort排序后的排列顺序：n);for(i=1;ilength;i+)printf(%dt,l-ri);/输出排序后数组和相关数据printf(关键字移动次数为：%dn,l-info);printf(关键字比较次数为：%dn,l-cmp);/*/int menu_select() /菜单目录int nu;char s;printf(*n);printf(*菜单*n);printf(1.bubblesortn); /冒泡排序printf(2.insertsortn); /直接插入排序printf(3.selectsortn); / 简单选择排序printf(4.qsorttn); /快速查找排序printf(5.shellsortn); /希尔排序printf(6.heapsortn); /堆排序printf(7.退出程序n);printf(*n);printf(请输入数字：1-7 选择相应的排序方式或操作：n); dos=getchar();nu=(int)s-48;while(nu55);return (nu);/*/void main()sqlist l,a,b,c,d,e; int i,dltamaxsize;int t=(int)(log(maxsize+1)/