1、實驗五排序算法設計和比較-、【實驗內容與要求】問題描述：利用直接插入排序、冒泡排序、快速排序對數列進行排序。基本要求：（1）能隨機生成30個值為0至到100的數。（2）用于排序的輸入數列可以是要求（1）中隨機生成的，也可以是鍵盤輸入。（3）輸出結果為利用三種方法排序后的結果，并能顯示三種算法時間、空間性能參數值?！緶y試數據】由隨機自行生成若干個數，進行排序。二、程序設計的基本思想，原理和算法描述:（包括程序的結構，數據結構，輸入/輸出設計，符號名說明等）1）符號說明:ml,m2,a,b,ctempnm3代表三種排序法的循環次數分別用來存儲三次排序的數據中間變量參與排序的數字個數maopao（a

2、，n）zhicha（b，n）quick（a,h,l）hl冒泡程序排序直接插入排序快速排序法分塊排序的上限分塊排序的下限2）程序說明（結構，輸入輸出）這個程序整個流程比較自然，一脈相傳，即先輸入要排序的個數，然后選擇要輸入的方式，將產生的數傳到數組中，然后依次地用冒泡子程序，直接插入的程序，快速排序的方法，依次排序，并將排好的數輸出，以及算法的時間復雜率。3）程序流程圖START初始化函數，根據提示語句，輸入要參加數字個數n同時將得到的數同步傳到數組b,c;為下面各種排序做準備調用冒泡排序的子;大到小，并計算循:程序，傳輸參數，排序從環的次數，將結果輸出1F調用直接插入子程序重復上面操作，輸出結

3、果。1r調用快速排序子程丿序,重復操作，輸出結果。三、源程序及注釋:#includestdio.h#includetime.hintm1=0;全局變量定義冒泡法循環的次數intm2=0;全局變量定義直接插入法循環的次數intm3=0;全局變量定義快速法循環的次數intsuiji(inta,intn);隨機生成目的數函數intij,temp;srand(unsigned)time(NULL);srand播下一個種子for(i=0;ivn;i+)ai=rand()%100;rand得到的數為0到100，依次傳到a中printf(%d,ai);jianpan(inta,intn)鍵盤輸入目的數函數i

4、ntij,k,l;for(i=0;ivn;i+)依次輸入目的數printf(input%dnumber:,i+1);scanf(%d,&ai);maopao(inta,intn)冒泡法排序程序intij,temp;for(i=0;ivn-1;i+)for(j=1jv(n-i);j+);具體的排序過程if(ajaj-1)temp=aj;aj=aj-1;aj-1=temp;m1+;計算循環次數printf(Bubbathesortednember:n);for(i=0;ivn;i+)printf(%d,ai);將排好的數依次顯示if(i+1)%5=0)printf(n);每輸出5個數換行print

5、f(timeeffective:%d,m1);輸出冒泡法的時間效率mlzhicha(intb,intn)直接插入排序子程序intij,temp;printf(nDirect:n);for(i=1;ivn;i+)temp=bi;for(j=i;j0&tempbj-1;-j)具體排序過程bj=bj-1;m2+;bj=temp;for(i=0;ivn;i+)printf(%d,bi);將排好的數顯示出來if(i+1)%5=0)printf(n);printf(timeeffective:%dn,m2);輸出時間效率quick(intc,intl,inth)快速排序法inttemp;intij,k;i

6、=lj=h;if(lh)temp=cl;whiie(ij)whiie(ij&cjvtemp);具體排序過程j-;m3+;if(ij)ci+=cj;whiie(itemp)i+;m3+;if(ij)cj-=ci;ci=temp;quick(cj,i-1);遞歸調用排序quick(cj+1,h);遞歸調用排序main()intij,k,n;inta100,b100,c1OO;定義三個數組來存放三種方法的數字cirscr();清屏函數printf(inputnumber:);scanf(%d,&n);輸入要參與排序的數目printf(chooseinputway(1.suiji2.jianpan):

7、);scanf(%d,&k);選擇輸入的方式if(k=1)k=1則調用隨機函數調用suiji(a,n);if(k=2)k=2則調用鍵盤輸入函數jianpan(a,n);for(i=0;ivn;i+)bi=ai;ci=ai;maopao(a,n);調用冒泡法程序zhicha(b,n);調用直接插入排序printf(Quicksort:n);quick(c,0,n-1);調用快速排序法for(i=0;ivn;i+)printf(%d,ci);if(i+1)%5=0)printf(n);printf(timeeffective:%d,m3);getchar();getchar();A四、運行輸出結果

8、：e9844sa7642O7bO2b2587eu9:?4l?iy8da4e733w17536erut3o8937iU5s7541tpcnC9242ei7h7642f1tfe733775367018937187541:7eu9242i97642t:7cter:9844fo97642fs7Cteke2587ec2P9742mi9iiu3353629374541:eu2421642tce844f642fe587e742mrl4-J48J6a2P914:24459:-恥6334378五、調試和運行程序過程中產生的問題及采取的措施：在寫程序的過程思路比較清晰，遇到的困難主要是編程軟件的不兼容，或是某些c語言規則在一些軟件上為非法的，早先我用的一直用地是devC+,但是在用隨機生成數子函數,一直提示有錯誤，改正不了，最后只好用最原始的turboC問題解決了，發現最好用的還是tc啊，以后只用突出（我電腦一直裝不了vc+,不知道怎么回事），在具體編程中需要考慮的是函數形參和實參的格式，一定要一致。六、對算法的程序的討論、分析，改進設想，其它經驗教訓:這次程序中主要用三種排序方法：a。冒泡排序b直接插入排序c?？焖倥判?。其中冒泡排序的時間復雜度：O(n2)空間復雜度：0(1)直接插入排序時間復雜度：0(說)空間復雜度：0(1)序法最差