数据结构课程设计排序算法比较

1、XXXXX双学数据结构课程设计报告排序算法比较一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结排序算法比较一、需求分析利用随机函数产生N个随机整数(N=500,1000,1500,2000,2500,30000),利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法(可添加其它排序方法)进行排序(结果为由小到大的顺序)，并统计每一种排序所耗费的时间(统计为图表坐标形式)。二、程序的主要功能1.用户输入任意个数，产生相应的随机数2.用户可以自己选择排序方式(直接插入排序、折半插入排序、起

2、泡排序、快速排序、选择排序、堆排序、基数排序)的一种3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。三、程序运行平台VisualC+6.0版本四、数据结构本程序的数据结构为线形表，线性顺序表、线性链表。O1、结构体：typedefstruct(int*r;/r指向线形表的第一个结点。r0闲置，不同的算法有不同的用处，如用作哨兵等。intlength;顺序表的总长度Sqlist;2、空线性表StatusInitSqlist(Sqlist&L)(L.r=(int*)malloc(MAXSIZE*sizeof(int);分配存储空间if(!L.r)(printf(存储分配失

3、败!);exit(0);存储分配失败L.length=0;/初始长度为0returnOK;)五、算法及时间复杂度(一)各个排序是算法思想：(1)直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。(2)折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序。(3)起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最

4、后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。(4)快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小， 则可分别对这两部分记录继续进行排序，已达到整个序列有序。(5)选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最小的记录，并和第I(1=I=N)个记录交换。(6)堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。(7)基数排序：按最低位

5、优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序(二)时间复杂度分析排序算法最差时间时间复杂度是否稳定？插入排序O(n2)O(n2)稳定冒泡排序O(n2)O(n2)稳定快速排序O(n2)O(n*log2n)不稳定选择排序O(n2)O(n2)稳定堆排序O(n*log2n)O(n*log2n)不稳定基数排序O(n*log2n)O(n2)稳定10000个数据的时间比较:算法名称直接插入排序用时0.25折半插入排序0.219起泡排序0.704快速排序0.016选择排序0.39堆排序0.0001基数排序0.016六、测试用例1、首先选择需要排序的数字个数，比如输入

6、50002、系统显示出随机产生的随机数。用户选择排序方式，比如选择1.直接插入排序( (S-|n|x|31098279239162Gls219029253163059137584S8322399113583572Q&7Q1S2?122342177B81387730406282951768624g382521571g23035728528428166782596S1012694923E426385276261715727374S411B93811593170963103344932976g27873299351993B092038121561257355842S9232849916731

7、11892544286066g5H28287260402276992231588164671268334(帕11158156B&169381946320920183E615758196859023202291929829ms654702317524196168399887619294632190B2?524692S519入入ffi嗝徘徘左.1.速择trtrtrtrAAffffffsAAffffffsffiufftffiufft速出直需快选堆基退、，,1234567812345678用半t-m5:并选询任阿请输入手排序的元素个数比5638算法排序比莪系统节统序trtr是地、，%*，123

8、4567812345678一:二3、系统将随机数排序后整齐的显示出来。296B82961329614296172961729621296432965629657296&92981296812970429731297332973429744297492975629761297fi32976829768297772978929790297952981229815298322983329849298552985529572985929S6629869298692987329876298812989129897299012?9092?910299162992y29935299422994229

9、947299542妙5629959299622997229975299772997929986299933晒330032300373003S3004130048300493006230066300S03映933009&301043D1D630199301143Q119301343013730145301693017530180301893019130195302113021230221302273022?3a2313023S口酿45302593027030271303083930130303393Q83032339333303353033G3034530350303973040&

10、;3041230422904243043238435304703047030499305023051030511305193052330524305273053830548305563056830574305813059130614306233062430630306433的4B3H6543的6430665306?4306933069530712307143072130731307323074230771307743077530783307963078730792307923080630S0?308113Q81430816308333日8333083630836308374、用户可以选择继续排

11、序或者退出系统七、程序源代码/*第六题：排序算法比较设计要求：利用随机函数产生N个随机整数(N=500,1000,1500,2000,2500,30000),利用直接插入排序、折半插入排序，起泡排序、快速排序、|选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。*/#includestdio.h#includestdlib.h#includetime.h/计时# defineERROR0# defineOK1# defineOVERFLOW-2# defineMAXSIZE用户自己规定排序的数字的长

12、度typedefintStatus;typedefstructint*r;/r0闲置intlength;/顺序表的总长度Sqlist;/构造一个空线性表StatusInitSqlist(Sqlist&L)L.r=(int*)malloc(MAXSIZE*sizeof(int);/分配存储空间if(!L.r)printf(存储分配失败！”)；exit(0);存储分配失败L.length=0;/初始长度为0returnOK;/输入随机数并显示在界面上StatusScanfSqlist(int&N,Sqlist&L)inti;printf(请输入要排序的元素个数N:);sca

13、nf(%d,&N);for(i=1;i=N;i+)L.ri=rand();/随机产生样本整数printf(nn);printf(随机产生了%d个随机数，它们是：n,N);for(i=1;i=N;i+)(printf(%7.2d,L.ri);)printf(n);L.length=N;/存储线性表的长度returnOK;)输出排序之后的数据StatusPrintfSqlist(intN,SqlistL)(inti;printf(数据个数：);/输出数据个数printf(%dn,L.length);printf(排序后的数据：(从左向右依次增大)n);/输出数据for(i=1;i=N;i+

14、)printf(%7.2d,L.ri);printf(n);returnOK;)*/直接插入排序/*StatusInsertSort(Sqlist&L)参考书P265算法10.1(inti,j;if(L.length=0)(printf(要排序的数据为空！);returnERROR;)for(i=2;i=L.length;i+)(if(L.riL.ri-1)将L.ri插入有序子表(L.r0=L.ri;复制为监视哨L.ri=L.ri-1;for(j=i-2;L.r0L.rj;j-)(L.rj+1=L.rj;记录后移)L.rj+1=L.r0;插入到正确位置)returnOK;)*/折半插入

15、排序/*StatusBInsertSort(Sqlist&L)参考书P267算法10.2(inti,j,mid,low,high;if(L.length=0)(printf(要排序的数据为空！);returnERROR;)for(i=2;i=L.length;i+)(L.r0=L.ri;将L.ri暂存在L.r0low=1;high=i-1;while(low=high)在rlow.high中折半查找有序插入的位置(mid=(low+high)/2;if(L.r0=high+1;j-)/插入点后的数据后移(L.rj+1=L.rj;/forreturnOK;/*希尔排序*/参考书P272算

16、法10.4及10.5/*StatusShellInsert(Sqlist&L,intdk)/希尔插入排序inti,j;/前后位置的增量是dkfor(i=dk+1;i=L.length;i+)L.rhigh+1=L.r0;/将数据插入/r0只是暂存单元，不是哨兵，if(L.ri0&L.r0L.rj;j-=dk)L.rj+dk=L.rj;记录后移，查找插入位置L.rj+dk=L.r0;/插入returnOK;StatusShellSort(Sqlist&L,intdlta5,intt)希尔排序inti;if(L.length=0)printf(要排序的数据为空！);retu

17、rnERROR;for(i=0;it;i+)ShellInsert(L,dltai);一趟增量为dltak的插入排序)returnOK;)*/*/起泡排序/*StatusBubbleSort(Sqlist&L)(inti,j,t;if(L.length=0)(printf(要排序的数据为空！);returnERROR;)for(i=1;i=L.length-1;i+)(for(j=1;jL.rj+1)前面的数据后面数据时(t=L.rj+1;L.rj+1=L.rj;L.rj=t;/将元素交换)returnOK;)/*/快速排序/*intPartition(Sqlist&L,int

18、low,inthigh)/交换顺序表中子表L.rlow.high的记录，使得枢轴记录到位，并返回其所在位置，此时在它之前(后)的记录均不大于它(intpivotkey;/记录关键字L.r0=L.rlow;用子表的第一个纪录作枢轴纪录pivotkey=L.rlow;用枢轴纪录关键字while(lowhigh)(while(low=pivotkey)(high-;)L.rlow=L.rhigh;/将比枢轴记录小的记录移到低端while(lowhigh&L.rlow=pivotkey)(low+;)L.rhigh=L.rlow;将比枢轴记录大的数移到高端)L.rlow=L.r0;/枢轴记录到

19、位returnlow;/Partition函数voidQsort(Sqlist&L,intlow,inthigh)(intpivotloc;if(lowhigh)长度大于1,可以进行(pivotloc=Partition(L,low,high);Qsort(L,low,pivotloc-1);/对低子表递归排序，pivotloc是枢轴位置Qsort(L,pivotloc+1,high);/对高子表递归排序)/Qsort函数StatusQuickSort(Sqlist&L)(if(L.length=0)(printf(要排序的数据为空！);returnERROR;Qsort(L,

20、1,L.length);returnOK;/QuickSort*/选择排序/*StatusChooseSort(Sqlist&L)(inti,j,k,t;if(L.length=0)(printf(没有数据！);returnERROR;for(i=1;i=L.length;i+)排序的趟数(k=i;for(j=i+1;j=L.length;j+)比较第i个元素以及其后的数据中最小的(if(L.rjL.rk)k=j;)if(i!=j)将最小数据赋值给L.ri(t=L.ri;L.ri=L.rk;L.rk=t;)returnOK;)*/堆排序/*StatusHeapAdjust(Sqlist

21、&L,ints,intm)调整L.rs的关键字，使L.rsm成大顶堆(inti;L.r0=L.rs;for(i=2*s;i+1=m;i*=2)沿数据较大的孩子结点向下筛选(if(im&L.ri=L.ri)/L.r0插入在S位置上break;L.rs=L.ri;s=i;)L.rs=L.r0;/插入新数据returnOK;)StatusHeapSort(Sqlist&L)堆排序(inti,t;if(L.length=0)(printf(没有数据！);returnERROR;)for(i=L.length/2;i0;i-)HeapAdjust(L,i,L.length);fo

22、r(i=L.length;i1;i-)(t=L.r1;将堆顶记录和当前未经排序的子序列L.r1.i中最后一个记录互换L.r1=L.ri;L.ri=t;HeapAdjust(L,1,i-1);将L.r1.i-1重新调整为大顶堆)returnOK;)*/基数排序/*typedefstructnodeintkey;node*next;RecType;StatusRadixSort(SqlistL)intt,i,j,k,d,n=1,m;RecType*p,*s,*q,*head10,*tail10;定义各链队的首尾指针for(i=1;ikey=L.ri;if(i=1)当为第一个元素时q=s;p=s;t

23、+;elseq-next=s;将链表连接起来q=s;t+;)q-next=NULL;d=1;while(n0)/将每个元素分配至各个链队(for(j=0;jkey/d;k=k%10;if(headk=NULL)/进行分配(headk=p;tailk=p;)else(tailk-next=p;tailk=p;)p=p-next;取下一个待排序的元素)p=NULL;用于收集第一个元素时的判断for(j=0;jnext=headj;q=tailj;)q-next=NULL;最后一个结点的next置为空d=d*10;n);n);n);printf(算法排序比较系统printf(printf(n=0;m

24、=1;while(mkey;i+;p=p-next;returnOK;*主函数*voidmain()(SqlistL;SqlistL0;InitSqlist(L);初始化LInitSqlist(L0);intm,i;charchoice=z;clock_tstart,finish;/doubleduration;向L中输入元素nprintf(printf(以下是各个排序算法的代号:nn);printf(1、直接插入排序n);printf(2、折半插入排序n);printf(3、起泡排序n);/*/定义clock_t用于计时printf(4、快速排序n);printf(5、选择排序n);prin

25、tf(6、堆排序n);printf(7、基数排序n);printf(8、退出该系统nn);ScanfSqlist(m,L0);printf(n);printf(1、直接插入排序n);printf(2、折半插入排序n);printf(3、起泡排序n);printf(4、快速排序n);printf(5、选择排序n);printf(6、堆排序n);printf(7、基数排序n);printf(8、退出该系统nn);printf(n请选择排序的方式，数子1-7:);scanf(%d,&choice);/选择排序方式赋值choice,用于后面的函数选择while(choice8)(printf(

26、输入方式有误。n请输入1-7选择排序方式，或者选择8退出系统);scanf(%d,&choice);while(choice!=8)(for(i=1;i=L0.length;i+)L.ri=L0.ri;L.length=L0.length;switch(choice)(case1:/直接插入排序start=clock();InsertSort(L);finish=clock();break;case2:/折半插入排序start=clock();BInsertSort(L);finish=clock();break;case3:/起泡排序start=clock();BubbleSort(L);finish=clock();break;case4:快速排序start=clock();QuickSort(L);finish=clock();break;case5:/选择排序start=clock();ChooseSort(L);finish=clock();break;case6:/堆排序start=clock();HeapSort(L);finish=clock();break;case7:/基数排序start=clock();RadixSort(L);finish=c