排序算法實驗報告材料

1、word實驗課程：算法分析與設(shè)計實驗名稱：幾種排序算法的平均性能比擬驗證型實驗實驗?zāi)繕耍?幾種排序算法在平均情況下哪一個更快。2加深對時間復(fù)雜度概念的理解。實驗任務(wù)：1實現(xiàn)幾種排序算法selectionsort, insertionsort,bottomupsort,quicksort, 堆排序。對于快 速分類，SPLIT中的劃分元素采用三者A(low), A(high), A( low+high)/2)中其值居中者。2隨機產(chǎn)生20組數(shù)據(jù)比如n=5000i, 1 i 20。數(shù)據(jù)均屬于 X圍0, 105內(nèi)的整 數(shù)。對于同一組數(shù)據(jù)，運行以上幾種排序算法，并記錄各自的運行時間以毫秒為單位。3根據(jù)實驗

2、數(shù)據(jù)與其結(jié)果來比擬這幾種分類算法的平均時間和比擬次數(shù)，并得出結(jié)論。實驗設(shè)備與環(huán)境：PC; C/C+等編程語言。實驗主要步驟：(1) 明確實驗?zāi)繕撕途唧w任務(wù)；(2) 理解實驗所涉與的幾個分類算法；(3) 編寫程序?qū)崿F(xiàn)上述分類算法；(4) 設(shè)計實驗數(shù)據(jù)并運行程序、記錄運行的結(jié)果;(5) 根據(jù)實驗數(shù)據(jù)與其結(jié)果得出結(jié)論；(6) 實驗后的心得體會。一:問題分析包括問題描述、建模、算法的根本思想與程序?qū)崿F(xiàn)的技巧等1:隨機生成n個0到100000的隨機數(shù)用來排序的算法如下.for(int n=1000;n20000;n+=1000)int a=new intn;for(int i=0;in;i+)ai=(i

3、nt) (Math.random()*100000);2.計算時間的類Date通過它的對象d1的getTime()得到當(dāng)前時間，再得到排序完成時的時間，相減得到排序所花的時間.Date d1=new Date();T=d2.getTime()-d1.getTime()3:排序算法 淇它count均表示排序中比擬的次數(shù). 插入排序主要算法如下int count=0;int c=new intb .1 ength;c0=b0;int j;for(int i=1;i=0&bicj;j-) count+;cj+1=cj;count+;cj+1=bi;選擇排序主要算法：int count=0;for(i

4、nt i=0;ib .1 ength;i+) int k=i;for(int j=i+1;jb .1 ength;j+)count+;if (bjbk)k=j;if(k!=i)int l;l=bi;bi=bk;bk=l;合并排序：static int merge(int a,int st,int ce,int fi)int count=0;/a表示數(shù)組,st表示要排序的數(shù)據(jù)的起點,ce表示第一局部的終點也是第二局部的起點,fi表示第二部份的終點int i=st;int j=ce;int cp=O;/由于數(shù)組c從0開始，而a是從st開始，并不一定是0.故要通過cp來表示c的第cp個值.int c

5、=new intfi-st;for(;ice;i+)for(;jaj) count+;ccp=aj;cp+;else break;ccp=ai;cp+;假如j的值還小于fi如此繼續(xù)把j到fi的值復(fù)制給c.此處也與書上的不同，主要由自己的理解來實現(xiàn)for(;jfi;j+)ccp=aj;cp+;/把得到的值復(fù)制到a數(shù)組上for(int k=0;kc .1 ength;k+)ast=ck;st+;return count;快速排序：用的方法與書上略有不同，主要通過spilt直接進展遞歸.static int spilt(int a,int low,int high) int count=0;int

6、i=low;int x=alow;for(int j=low+1;jv=high;j+)if(aj=x)count+;i=i+1;if(i!=j)int temp=ai;ai=aj; aj=temp;int temp= alow;alow=ai;ai=temp;int w=i;/此處的if語句可以減少很多不必要的排if(lowlow)count=count+spilt(a,low,w-1);序,例如只剩下一個數(shù)字時就不必再用spilt來排序了if(w+1high)count=count+spilt(a,w+1,high);return count;:實驗數(shù)據(jù)與其結(jié)果可用圖表形式給出數(shù)插入排序選

7、擇排序合并排序快速排序比擬次數(shù)時間比擬次數(shù)時間比擬次數(shù)時間比擬次數(shù)時間1000246415 3毫秒499500 2毫秒42921毫秒6042 0毫秒排序個堆排序比擬次數(shù)時間53361 毫秒2000987905 4 毫秒1999000 5 毫秒138950毫秒12502 1毫秒172511毫秒300022212537毫秒4498500 9 毫秒289111毫秒18072 1毫秒357381毫秒4000397480712毫秒7998000 16毫秒500871毫秒27763 0毫秒613891毫秒5000633074017毫秒12497500 24毫秒767192毫秒31673 0毫秒941190

8、毫秒6000900082226毫秒17997000 33毫秒1095151毫秒38876 1毫秒1343651毫秒70001236164934毫秒24496500 44毫秒1487921毫秒52786 1毫秒1820491毫秒80001619570146毫秒31996000 59毫秒1952612毫秒54716 0毫秒2374561毫秒90002031273058毫秒40495500 75毫秒2473952毫秒78117 1毫秒3004441毫秒100002472051070毫秒49995000 91毫秒3057281毫秒80273 1毫秒3708431毫秒110002993784884毫秒6

9、0494500 113毫秒3705174毫秒89960 1毫秒4488411毫秒1200036256786104毫秒71994000 133毫秒4422322毫秒107707 1 毫秒5350302毫秒1300042587471120毫秒84493500 155毫秒5204922毫秒102860 1 毫秒6291741毫秒1400049063373139毫秒97993000 177毫秒6058062毫秒125364 1 毫秒7311911毫秒1500056280216161毫秒112492500 201毫秒6985463毫秒134152 2 毫秒8414923毫秒160006420513718

10、5毫秒127992000 228J毫秒7994102毫秒135362 1 毫秒9604001毫秒1700072750562206毫秒144491500 258J毫秒9068383毫秒144717 1 毫秒10870132毫秒1800080846587231毫秒161991000 288J毫秒10201363毫秒164631 2 毫秒12216992毫秒1900090537142264毫秒180490500 321毫秒11397575毫秒168298 2 毫秒13642302毫秒三:實驗結(jié)果分析與結(jié)論：實和堆排序處于不確定的情況，不穩(wěn)定性比擬明顯但是是一種比擬快的算法.四:實驗自我評價與心得體會：通過本實驗，我發(fā)現(xiàn)以前經(jīng)常使用的冒泡排序，選擇排序等排序方法在遇到大量的數(shù)據(jù)的時候顯示出來的嚴重的不足，