數(shù)據(jù)結構課程設計排序算法比較

1、XXXXX雙學數(shù)據(jù)結構課程設計報告排序算法比較一、需求分析二、程序的主要功能三、程序運行平臺四、數(shù)據(jù)結構五、算法及時間復雜度六、測試用例七、程序源代碼二感想體會與總結排序算法比較一、需求分析利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)(N=500,1000,1500,2000,2500,30000),利用直接插入排序、折半插入排序，起泡排序、快速排序、選擇排序、堆排序，基數(shù)排序七種排序方法(可添加其它排序方法)進行排序(結果為由小到大的順序)，并統(tǒng)計每一種排序所耗費的時間(統(tǒng)計為圖表坐標形式)。二、程序的主要功能1.用戶輸入任意個數(shù)，產(chǎn)生相應的隨機數(shù)2.用戶可以自己選擇排序方式(直接插入排序、折半插入排序、起

2、泡排序、快速排序、選擇排序、堆排序、基數(shù)排序)的一種3.程序給出原始數(shù)據(jù)、排序后從小到大的數(shù)據(jù)，并給出排序所用的時間。三、程序運行平臺VisualC+6.0版本四、數(shù)據(jù)結構本程序的數(shù)據(jù)結構為線形表，線性順序表、線性鏈表。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)直接插入排序：將一個記錄插入到已排好的有序表中，從而得到一個新的，記錄數(shù)增加1的有序表。(2)折半插入排序：插入排序的基本插入是在一個有序表中進行查找和插入，這個查找可利用折半查找來實現(xiàn)，即為折半插入排序。(3)起泡排序：首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序，則將兩個記錄交換，然后比較第二個記錄和第三個記錄的關鍵字。依此類推，直到第N-1和第N個記錄的關鍵字進行過比較為止。上述為第一趟排序，其結果使得關鍵字的最大紀錄被安排到最

4、后一個記錄的位置上。然后進行第二趟起泡排序，對前N-1個記錄進行同樣操作。一共要進行N-1趟起泡排序。(4)快速排序：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小， 則可分別對這兩部分記錄繼續(xù)進行排序，已達到整個序列有序。(5)選擇排序：通過N-I次關鍵字間的比較，從N-I+1個記錄中選出關鍵字最小的記錄，并和第I(1=I=N)個記錄交換。(6)堆排序：在堆排序的算法中先建一個大頂堆，既先選得一個關鍵字作為最大的記錄并與序列中最后一個記錄交換，然后對序列中前N-1記錄進行選擇，重新將它調(diào)整成一個大頂堆，如此反復直到排序結束。(7)基數(shù)排序：按最低位

5、優(yōu)先法先對低位關鍵字進行排序，直到對最高位關鍵字排序為止，經(jīng)過若干次分配和收集來實現(xiàn)排序(二)時間復雜度分析排序算法最差時間時間復雜度是否穩(wěn)定？插入排序O(n2)O(n2)穩(wěn)定冒泡排序O(n2)O(n2)穩(wěn)定快速排序O(n2)O(n*log2n)不穩(wěn)定選擇排序O(n2)O(n2)穩(wěn)定堆排序O(n*log2n)O(n*log2n)不穩(wěn)定基數(shù)排序O(n*log2n)O(n2)穩(wěn)定10000個數(shù)據(jù)的時間比較:算法名稱直接插入排序用時0.25折半插入排序0.219起泡排序0.704快速排序0.016選擇排序0.39堆排序0.0001基數(shù)排序0.016六、測試用例1、首先選擇需要排序的數(shù)字個數(shù)，比如輸入

6、50002、系統(tǒng)顯示出隨機產(chǎn)生的隨機數(shù)。用戶選擇排序方式，比如選擇1.直接插入排序( (S-|n|x|31098279239162Gls219029253163059137584S8322399113583572Q&7Q1S2?122342177B81387730406282951768624g382521571g23035728528428166782596S1012694923E426385276261715727374S411B93811593170963103344932976g27873299351993B092038121561257355842S9232849916731

7、11892544286066g5H28287260402276992231588164671268334(帕11158156B&169381946320920183E615758196859023202291929829ms654702317524196168399887619294632190B2?524692S519入入ffi嗝徘徘左.1.速擇trtrtrtrAAffffffsAAffffffsffiufftffiufft速出直需快選堆基退、，,1234567812345678用半t-m5:并選詢?nèi)伟⒄堓斎胧峙判虻脑貍€數(shù)比5638算法排序比莪系統(tǒng)節(jié)統(tǒng)序trtr是地、，%*，123

8、4567812345678一:二3、系統(tǒng)將隨機數(shù)排序后整齊的顯示出來。296B82961329614296172961729621296432965629657296&92981296812970429731297332973429744297492975629761297fi32976829768297772978929790297952981229815298322983329849298552985529572985929S6629869298692987329876298812989129897299012?9092?910299162992y29935299422994229

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

10、;3041230422904243043238435304703047030499305023051030511305193052330524305273053830548305563056830574305813059130614306233062430630306433的4B3H6543的6430665306?4306933069530712307143072130731307323074230771307743077530783307963078730792307923080630S0?308113Q81430816308333日8333083630836308374、用戶可以選擇繼續(xù)排

11、序或者退出系統(tǒng)七、程序源代碼/*第六題：排序算法比較設計要求：利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)(N=500,1000,1500,2000,2500,30000),利用直接插入排序、折半插入排序，起泡排序、快速排序、|選擇排序、堆排序，基數(shù)排序七種排序方法（可添加其它排序方法）進行排序（結果為由小到大的順序），并統(tǒng)計每一種排序所耗費的時間（統(tǒng)計為圖表坐標形式）。*/#includestdio.h#includestdlib.h#includetime.h/計時# defineERROR0# defineOK1# defineOVERFLOW-2# defineMAXSIZE用戶自己規(guī)定排序的數(shù)字的長

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;/輸入隨機數(shù)并顯示在界面上StatusScanfSqlist(int&N,Sqlist&L)inti;printf(請輸入要排序的元素個數(shù)N:);sca

13、nf(%d,&N);for(i=1;i=N;i+)L.ri=rand();/隨機產(chǎn)生樣本整數(shù)printf(nn);printf(隨機產(chǎn)生了%d個隨機數(shù)，它們是：n,N);for(i=1;i=N;i+)(printf(%7.2d,L.ri);)printf(n);L.length=N;/存儲線性表的長度returnOK;)輸出排序之后的數(shù)據(jù)StatusPrintfSqlist(intN,SqlistL)(inti;printf(數(shù)據(jù)個數(shù)：);/輸出數(shù)據(jù)個數(shù)printf(%dn,L.length);printf(排序后的數(shù)據(jù)：(從左向右依次增大)n);/輸出數(shù)據(jù)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(要排序的數(shù)據(jù)為空！);returnERROR;)for(i=2;i=L.length;i+)(if(L.riL.ri-1)將L.ri插入有序子表(L.r0=L.ri;復制為監(jiān)視哨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(要排序的數(shù)據(jù)為空！);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-)/插入點后的數(shù)據(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;/將數(shù)據(jù)插入/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(要排序的數(shù)據(jù)為空！);retu

17、rnERROR;for(i=0;it;i+)ShellInsert(L,dltai);一趟增量為dltak的插入排序)returnOK;)*/*/起泡排序/*StatusBubbleSort(Sqlist&L)(inti,j,t;if(L.length=0)(printf(要排序的數(shù)據(jù)為空！);returnERROR;)for(i=1;i=L.length-1;i+)(for(j=1;jL.rj+1)前面的數(shù)據(jù)后面數(shù)據(jù)時(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;將比樞軸記錄大的數(shù)移到高端)L.rlow=L.r0;/樞軸記錄到

19、位returnlow;/Partition函數(shù)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函數(shù)StatusQuickSort(Sqlist&L)(if(L.length=0)(printf(要排序的數(shù)據(jù)為空！);returnERROR;Qsort(L,

20、1,L.length);returnOK;/QuickSort*/選擇排序/*StatusChooseSort(Sqlist&L)(inti,j,k,t;if(L.length=0)(printf(沒有數(shù)據(jù)！);returnERROR;for(i=1;i=L.length;i+)排序的趟數(shù)(k=i;for(j=i+1;j=L.length;j+)比較第i個元素以及其后的數(shù)據(jù)中最小的(if(L.rjL.rk)k=j;)if(i!=j)將最小數(shù)據(jù)賦值給L.ri(t=L.ri;L.ri=L.rk;L.rk=t;)returnOK;)*/堆排序/*StatusHeapAdjust(Sqlist

21、&L,ints,intm)調(diào)整L.rs的關鍵字，使L.rsm成大頂堆(inti;L.r0=L.rs;for(i=2*s;i+1=m;i*=2)沿數(shù)據(jù)較大的孩子結點向下篩選(if(im&L.ri=L.ri)/L.r0插入在S位置上break;L.rs=L.ri;s=i;)L.rs=L.r0;/插入新數(shù)據(jù)returnOK;)StatusHeapSort(Sqlist&L)堆排序(inti,t;if(L.length=0)(printf(沒有數(shù)據(jù)！);returnERROR;)for(i=L.length/2;i0;i-)HeapAdjust(L,i,L.length);fo

22、r(i=L.length;i1;i-)(t=L.r1;將堆頂記錄和當前未經(jīng)排序的子序列L.r1.i中最后一個記錄互換L.r1=L.ri;L.ri=t;HeapAdjust(L,1,i-1);將L.r1.i-1重新調(diào)整為大頂堆)returnOK;)*/基數(shù)排序/*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(算法排序比較系統(tǒng)printf(printf(n=0;m

24、=1;while(mkey;i+;p=p-next;returnOK;*主函數(shù)*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、基數(shù)排序n);printf(8、退出該系統(tǒng)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、基數(shù)排序n);printf(8、退出該系統(tǒng)nn);printf(n請選擇排序的方式，數(shù)子1-7:);scanf(%d,&choice);/選擇排序方式賦值choice,用于后面的函數(shù)選擇while(choice8)(printf(

26、輸入方式有誤。n請輸入1-7選擇排序方式，或者選擇8退出系統(tǒng));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:/基數(shù)排序start=clock();RadixSort(L);finish=c