大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序算法比較

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

2、序、快速排序、選擇排序、堆排序、基數(shù)排序）的一種.程序給出原始數(shù)據(jù)、排序后從小到大的數(shù)據(jù)，并給出排序所用的時間。三、程序運行平臺VisualC+版本四、數(shù)據(jù)結(jié)構(gòu)本程序的數(shù)據(jù)結(jié)構(gòu)為線形表，線性順序表、線性鏈表。O1、結(jié)構(gòu)體：typedefstruct口用時各個算法排序用時0.2 u=0.01G-1E-Q50.010或推入庠忻后插入3序起:泡排營I，國畫專金捽排丁號屋羲?？谟玫膢IL加|5219|U.TMUJ1B0-391E-0S0,U16算法腔岸法推序比較系統(tǒng)IJT 一二三 用黑入入ttt窄徘徘韭孑*速出宜嘉快霍基退12345678殖輸入要排序的元素T數(shù)N：50g0插入排序31098279239

3、16261821902?45832239911353S72037013877282951768fi24037285264281652E9G01012762617157273748411S93844932768278732993519109257395584259232849916731685B2S2S726040227699223343S11158156061946319FSS弓M232H2291929R2935*i16839988761929463219目25316152718252209491159311849158820920S47R82753059223421571823M170962

4、B3S12544216467183662A17S24691375817780230353103321561B&B&1208315758241號E2551912345678二；S-HJII直需快選堆基退入入tfF1JTI-二le.3、系統(tǒng)將隨機數(shù)排序后整齊的顯示出來。2960829&1329614296172961729621296432965G29657296582966929681298129704297312973329734297442974?2?5629761Z9763297682976829777297B92979029795298122981529832298332?8492985

5、5298552985729B59N986E29S6929Sg92987329876298812989129897299A129909299102?1629929299352?942299422994?29954Z995&29959299E229972299752997729979299BC2999329996360033003230B37300383Q041300483904930M2390G63308930B9330酎6301043Q10&301B?301142B119301343013730145301g930175301S0301883取觸301913019530211302123目22

6、1獨227302273B2313923S3024530259102603027038271303003630130363303083032330333303353033&30338303453B35930377304063GH123B4233B424384323必53046&3047030470304993居毗3951030511305193&2330524305273115363Q5483匣BG305683B5743058130591306143062338624306303B643396543866430665306743069339&9S307123m430721307313073230

7、74230771307743077530783307863078730792307923080630807308113D81430816308333B8333083630836308374、用戶可以選擇繼續(xù)排序或者退出系統(tǒng)。七、程序源代碼/*第六題：排序算法比較設(shè)計要求：利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)（N=500,1000,1500,2000,2500,30000）,利用直接插入排序、折半插入排序，起泡排序、快速排序、|選擇排序、堆排序，基數(shù)排序七種排序方法（可添加其它排序方法）進行排序（結(jié)果為由小到大的順序），并統(tǒng)計每一種排序所耗費的時間（統(tǒng)計為圖表坐標(biāo)形式）。*/#include#inclu

8、de#includehigh中折半查找有序插入的位置mid=(low+high)/2;if0mid）high的記錄，使得樞軸記錄到位，并返回其所在位置，此時在它之前（后）的記錄均不大于它intpivotkey;i中最后一個記錄互換1=i；i=t;HeapAdjust(L,1,i-1);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;/定義各鏈隊的首尾指針

9、for(i=1;ikey=i;if(i=1)/當(dāng)為第一個元素時q=s;p=s;t+;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;elsetailk-next=p;tailk=p;p=p-next;/取下一個待排序的元素p=NULL;/用于收集第一個元素時的判斷for(j=0;jnext=headj;q=tailj;q-next=NULL;/最后一個結(jié)點的next置為空d=d*10;n=0;m=1

10、;while(mkey;i+;p=p-next;)returnOK;*/主函數(shù)/*voidmain()SqlistL;SqlistL0;InitSqlist(L);初始化LInitSqlist(L0);intm,i;charchoice=z;clock_tstart,finish;/定義clock_t用于計時doubleduration;向L中輸入元素n printf( printf( printf(算法排序比較系統(tǒng)n);n);n);f(以下是各個排序算法的代號：nn);printf(1、直接插入排序n);printf(2、折半插入排序n);printf(3、起泡排序n);printf(4、快

11、速排序n);printf(5、選擇排序n);printf(6、堆排序n);printf(7、基數(shù)排序n);8、退出該系統(tǒng)nn);printf(ScanfSqlist(m,L0);printf(1、直接插入排序n);printf(2、折半插入排序n);printf(3、起泡排序n);printf(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ù)選擇w

12、hile(choice8)printf(輸入方式有誤。n請輸入1-7選擇排序方式，或者選擇8退出系統(tǒng))scanf(%d,&choice);while(choice!=8)for(i=1;i=;i+)i=i;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();brea

13、k;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=clock();break;case8:/直接退出break;PrintfSqlist(m,L);/輸出數(shù)據(jù)和L的長度duration=(double)(

14、finish-start)/CLOCKS_PER_SEC;/輸出算術(shù)時間printf(n本次排序運算所用的時間是：%lfsecondsn,duration);printf（本次排序結(jié)束。n）;printf（n）;printf（繼續(xù)本系統(tǒng)嗎nn）;printf（以下是各個排序算法的代號：n）; TOC o 1-5 h z 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)n）;printf（n請請輸入1-7選擇排序方式，或者選擇8退出系統(tǒng):）;scanf（%d,&choice）;while（choice8）printf（輸入方式有誤。n請輸入1-7選擇排序方式，或者選擇8退出系統(tǒng)）;scanf(%d,&choice);感想體會與總結(jié)好的算法+編程技巧+高效率=好的程序。1、做什么都需要耐心，做設(shè)計寫程序更需要耐心。一開始的時候，我寫函數(shù)寫的很快，可是等最后調(diào)試的時候發(fā)現(xiàn)錯誤很隱蔽，就很費時間了。后來我先在紙上構(gòu)思出函數(shù)的功能和參數(shù)，考慮好接口之后才動手編，這樣就比較容易成功了。2、做任何事情我決定都應(yīng)該有個總體規(guī)劃。之后的工作按照規(guī)劃逐步展開完成。對于一