數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(共33頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課 程 設(shè) 計(jì) 說(shuō) 明 書(shū)課程名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu)和算法 設(shè)計(jì)題目： 多種排序 院 系： 計(jì)算機(jī)科學(xué)與信息工程學(xué)院 學(xué)生姓名： 學(xué) 號(hào)： 專(zhuān)業(yè)班級(jí)： 計(jì)科嵌入式（12-1） 指導(dǎo)教師： 年 月 日專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)課 程 設(shè) 計(jì) 任 務(wù) 書(shū)設(shè)計(jì)題目表達(dá)式計(jì)算程序設(shè)計(jì)學(xué)生姓名所在院系計(jì)科專(zhuān)業(yè)、年級(jí)、班12計(jì)科（嵌入式）設(shè)計(jì)要求：1) 采用如下七種方法實(shí)現(xiàn)上述問(wèn)題求解：插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序。2) 統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。并將數(shù)據(jù)序列和不同的查找算法的性能結(jié)果記錄入t

2、xt文件。學(xué)生應(yīng)完成的工作：1. 利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（10000以上）。2. 對(duì)這些數(shù)字進(jìn)行排序。3. 采用插入、希爾、起泡、快速、選擇、歸并、堆排序方法解決問(wèn)題。4. 對(duì)不同的排序算法進(jìn)行性能比較并記錄。參考文獻(xiàn)閱讀： 1. 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 嚴(yán)蔚敏 清華大學(xué)出版社 2. C語(yǔ)言程序設(shè)計(jì) 丁峻嶺 中國(guó)鐵道出版社 3. C程序設(shè)計(jì) 譚浩強(qiáng) 清華大學(xué)出版社工作計(jì)劃：任務(wù)下達(dá)日期： 年 月 日 任務(wù)完成日期： 年 月 日指導(dǎo)教師（簽名）： 學(xué)生（簽名）： 多種排序摘 要： 排序是算法中最基礎(chǔ)的問(wèn)題之一，經(jīng)典的排序算法是前人不斷總結(jié)得到的，基于比較的方法是比較直觀的方式，主要存在插入法

3、排序、堆排序、希爾排序、歸并排序、快速排序，每一種排序算法都有自己的優(yōu)缺點(diǎn)，比如插入法排序適用于那些長(zhǎng)度短的排序，要是長(zhǎng)的話，有些愛(ài)莫能助啦，堆排序主要是依據(jù)了二叉堆的特性，但是創(chuàng)建堆的過(guò)程也是一個(gè)復(fù)雜的問(wèn)題，希爾排序的過(guò)程是一個(gè)不斷精確的過(guò)程，但是目前也只是一個(gè)經(jīng)驗(yàn)方式。歸并排序是一個(gè)遞歸的問(wèn)題，采用分治的思想實(shí)現(xiàn)，但是這種算法需要額外的存儲(chǔ)空間，快速排序雖然是實(shí)踐中比較常用的算法，但是對(duì)于有序的數(shù)組采用快速排序就是災(zāi)難。比較型算法的時(shí)間復(fù)雜度最優(yōu)也只能到達(dá)O(NlogN)。關(guān)鍵詞：歸并排序快排排序選擇排序冒泡排序插入排序堆排序希爾排序內(nèi)部排序目 錄 501. 設(shè)計(jì)背景1.1問(wèn)題描述 利用隨

4、機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（10000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。包括：插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序。1.2 問(wèn)題分析經(jīng)典的排序算法是前人不斷總結(jié)得到的，基于比較的方法是比較直觀的方式，主要存在插入法排序、堆排序、希爾排序、歸并排序、快速排序，每一種排序算法都有自己的優(yōu)缺點(diǎn)。2. 設(shè)計(jì)方案2.1 算法設(shè)計(jì)（1） 選擇排序 在待排序的一組數(shù)據(jù)元素中，選出最小的一個(gè)數(shù)據(jù)元素與第一個(gè)位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當(dāng)中再找最小的與第二個(gè)位置的數(shù)據(jù)元素交換，循環(huán)到只剩下最后一個(gè)數(shù)據(jù)元素為止。 （2） 冒泡排序 相鄰的兩個(gè)元素進(jìn)行比較，將小的調(diào)到前面，

5、大的調(diào)到后面。 （3） 插入排序 待排序的記錄放在數(shù)組R0n-1中排序過(guò)程中某一時(shí)刻，R被劃分成兩個(gè)子區(qū)間R0,i-1 (有序和)Rin-1(無(wú)序)。直接插入的基本操作是將當(dāng)前無(wú)序區(qū)的一個(gè)記錄Ri插入到有序區(qū)R0i-1中適當(dāng)?shù)奈恢?（4） 快速排序 在待排序的數(shù)組的n個(gè)元素中取一個(gè)元素(一般取第一個(gè))，將其移動(dòng)到這樣的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，這樣是一趟快速排序；然后對(duì)數(shù)組的兩個(gè)部分進(jìn)行同樣的操作，直到每部分只有一個(gè)記錄為止；總之，每趟使表的第一個(gè)元素放在適當(dāng)位置，將表兩分，再對(duì)兩子表進(jìn)行同樣的遞歸劃分，直至劃分的子表長(zhǎng)度為1。（5）堆排序堆排序中 heap 算

6、法的時(shí)間復(fù)雜度與堆所對(duì)應(yīng)的完全二叉樹(shù)的樹(shù)高度 log2n 相關(guān)。而 heapsort 中對(duì) heap 的調(diào)用數(shù)量級(jí)為n，所以堆排序的整個(gè)時(shí)間復(fù)雜度為O(nlog2n) 。并且堆排序是不穩(wěn)定的。堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無(wú)序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡(jiǎn)單。（6）歸并排序 將兩個(gè)或兩個(gè)以上的有序表組成一個(gè)新的有序表。 （7） 希爾排序?qū)o(wú)序數(shù)組分割為若干個(gè)子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，對(duì)各個(gè)子序列進(jìn)行插入排序；然后再選擇一個(gè)更小的增量，再將數(shù)組分割為多個(gè)子序列進(jìn)行排序.最后選擇增量為1，即使用直接插入排序

7、，使最終數(shù)組成為有序。增量的選擇：在每趟的排序過(guò)程都有一個(gè)增量，至少滿足一個(gè)規(guī)則 增量關(guān)系 d1 > d2 > d3 >.> dt = 1 (t趟排序)；根據(jù)增量序列的選取其時(shí)間復(fù)雜度也會(huì)有變化，這個(gè)不少論文進(jìn)行了研究，在此處就不再深究；本文采用首選增量為n/2,以此遞推，每次增量為原先的1/2，直到增量為1。2.2 功能模塊分析1. 數(shù)據(jù)輸入：采取隨機(jī)函數(shù)實(shí)現(xiàn)輸入數(shù)據(jù)表。int input_num()printf("您要給多少個(gè)數(shù)排序？ntt");scanf("%d",&data_num);srand(NULL);pri

8、ntf("隨機(jī)產(chǎn)生%d個(gè)數(shù):ntt",data_num);for(int i=1;i<=data_num;i+)data_arrayi=rand()%; printf("%dn",data_arrayi);oldi=data_arrayi; printf("ntt");2. 數(shù)據(jù)輸出：for循環(huán)輸出即可。int outnew0()printf("排序后的結(jié)果為:");for(int i=data_num;i>=1;i-)printf("%d%s",data_arrayi,i!=1?&

9、quot; ":"n");其中增加了輸出空格與換行區(qū)別。3. 主界面實(shí)現(xiàn)：printf("DATE:May twenty 2014n"); printf("All Copyright Reserved 2014-2015 Wang Guangchun n"); printf("ADDRESS: 604 AYITrnnn"); printf(" n"); printf("各種排序比較 n"); printf("默認(rèn)從大到小輸出，可以選擇9進(jìn)行切換n"

10、;); printf(" n"); printf(" * * n"); printf(" * * * n"); printf(" * * n"); printf(" * 520 * n"); printf(" * 歡迎 * n"); printf(" * 使用 * n"); printf(" * * n"); printf(" * n"); printf("歡迎再次使用!nrn"); printf

11、("*n"); printf("* . . . . . *n"); printf("* . . . . . . *n"); printf("* . . . . . . *n"); printf("* . . . . . . *n"); printf("* . . . . *n"); printf("*n");4. 人機(jī)交互界面：printf("n n");printf("請(qǐng)輸入指令 n");printf("

12、* n");printf("$ 1.快速排序 $ n");printf("$ 2.歸并排序 $ n");printf("$ 3.堆排序 $ n");printf("$ 4.希爾排序 $ n");printf("$ 5.插入排序 $ n");printf("$ 6.選擇排序 $ n");printf("$ 7.冒泡排序 $ n");printf("$ 8.重新隨機(jī)輸入 $ n");printf("$ 9.選擇排序方式

13、$ n");printf("* n");printf(" 0.退出 n");printf(" n");printf("請(qǐng)選擇：n"); printf("請(qǐng)輸入指令 n"); printf("* n"); printf("$ 1.從小到大 $ n"); printf("$ 0.從大到小 $ n"); printf("* n"); printf(" 87.退出 n"); printf(&qu

14、ot; n"); printf("請(qǐng)選擇：n");5. 排序方法的實(shí)現(xiàn)：（1）選擇排序void chose_sort(int a,int n)int min,temp;for(int i=0;i<n;i+)min=i;for(int j=i;j<n;j+)if(amin>aj)min=j;temp=amin; amin=ai;ai=temp;（2） 希爾排序void ShellInsert(int *a,int d,int n)for (int i=d;i<n;i+)/從第2個(gè)數(shù)據(jù)開(kāi)始插入int j=i-d;int temp=ai;/記錄要

15、插入的數(shù)據(jù)while(j >= 0&&aj>temp)/從后向前，找到比其小的數(shù)的位置aj+d=aj;/向后挪動(dòng)j-=d;if(j!=i-d)/存在比其小的數(shù)aj+d=temp;void ShellSort(int* a,int n)int d=n/2;/初始增量設(shè)為數(shù)組長(zhǎng)度的一半while(d>=1)ShellInsert(a,d,n);d=d/2;/每次增量變?yōu)樯洗蔚亩种唬?） 歸并排序：void _merge(int a,int first,int mid,int last,int temp)int i=first,j=mid+1,m=mid,n=l

16、ast,k=0;while(i<=m&&j<=n)if(ai<=aj)tempk+=ai+;elsetempk+=aj+;while(i<=m)tempk+=ai+;while(j<=n)tempk+=aj+;for(i=0;i<k;i+)afirst+i=tempi;void MergeSort(int a,int first,int last,int temp) if(first<last) int mid=(first+last)/2; MergeSort(a,first,mid,temp); MergeSort(a,mid+1,

17、last,temp); _merge(a,first,mid,last,temp); bool MergeSort(int a,int n) int *p=new intn; if(p=NULL) return false; else MergeSort(a,0,n-1,p); delete p; return true; （4） 堆排序：void HeapAdjust(int *a,int i,int size)/調(diào)整堆 int lchild=2*i;/i的左孩子節(jié)點(diǎn)序號(hào) int rchild=2*i+1;/i的右孩子節(jié)點(diǎn)序號(hào) int max=i;/臨時(shí)變量 if(i<=size/2)

18、/如果i是葉節(jié)點(diǎn)就不用進(jìn)行調(diào)整 if(lchild<=size&&alchild>amax) max=lchild; if(rchild<=size&&archild>amax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size);/避免調(diào)整之后以max為父節(jié)點(diǎn)的子樹(shù)不是堆 void BuildHeap(int *a,int size)/建立堆 int i; for(i=size/2;i>=1;i-)/非葉節(jié)點(diǎn)最大序號(hào)值為size/2 HeapAdjust(a,i

19、,size);void HeapSort(int *a,int size)/堆排序 int j=1; BuildHeap(a,size); for(int i=size;i>=1;i-) swap(a1,ai); /交換堆頂和最后一個(gè)元素，即每次將剩余元素中的最大者放到最后面 /BuildHeap(a,i-1); /將余下元素重新建立為大頂堆 HeapAdjust(a,1,i-1); /重新調(diào)整堆頂節(jié)點(diǎn)成為大頂堆 （5） 冒泡排序：void maopao()int temp;for(int i=1;i<=data_num;i+)for(int j=i+1;j<=data_nu

20、m;j+)if(data_arrayi>data_arrayj)temp=data_arrayi;data_arrayi=data_arrayj;data_arrayj=temp;（6） 插入排序：void charu()int i,j;int temp; printf("插入排序:n");for(i=1;i<=data_num;i+)int temp=data_arrayi;for (j=i;j>0 && temp<data_arrayj-1;j-)data_arrayj=data_arrayj-1;data_arrayj=temp

21、;if(!t) outnew0();else outnew1();（7） 快速排序：void kuaisu1()/快速排序1 printf("快速排序:n"); sort(data_array+1,data_array+data_num+1); if(!t) outnew0();else outnew1();3.主要算法流程圖 主程序產(chǎn)生1組隨機(jī)數(shù)將隨機(jī)數(shù)保存在數(shù)組中希爾排序堆排序冒泡排序選擇排序插入排序歸并排序快速排序選擇排序方式輸出無(wú)序數(shù)組排序后的結(jié)果選擇操作方式4. 結(jié)果與結(jié)論4.1 正確結(jié)果1. 主界面 人機(jī)交互2. 輸入界面3. 選擇排序方式4. 輸出結(jié)果5. 退

22、出界面4.2錯(cuò)誤信息5. 算法復(fù)雜度以及穩(wěn)定性分析下圖反映了不同算法排序的時(shí)間復(fù)雜度的級(jí)別及其空間復(fù)雜度和穩(wěn)定性。算法名稱(chēng)平均時(shí)間輔助空間穩(wěn)定性O(shè)(n2)O(1)是O(n2)O(1)否O(n2)O(1)是O(nlog2n)O(n)是O(nlog2n)O(n)否O(nlog2n)O(1)否O(1)否下圖表明了各種算法在不同數(shù)據(jù)規(guī)模下，完成排序所消耗的時(shí)間（毫秒為單位），從表中可以顯然看出O(n2)的排序算法比O(nlog2n)的算法 時(shí)間多出幾百上千倍，而且隨著數(shù)據(jù)數(shù)據(jù)規(guī)模增大時(shí)間比也會(huì)隨著增大；因?yàn)榕判虻臄?shù)據(jù)采用隨機(jī)數(shù)，順序?qū)⒈淮騺y，快速排序算法優(yōu)于其他排序算法。算法名稱(chēng)1萬(wàn)2萬(wàn)3萬(wàn)4萬(wàn)5萬(wàn)6

23、萬(wàn)7萬(wàn)8萬(wàn)9萬(wàn)10萬(wàn)冒泡排序14425497122062186134017491486739488880選擇排序19981617903254506271669645126361610219643插入排序17871716282882445864468822116491454717914歸并排序36912151822262833快速排序25811141821252932堆排序371216192326303437希爾排序3811152424293540416. 收獲與致謝通過(guò)這次課程設(shè)計(jì)作業(yè)我著實(shí)感受了一次編程的樂(lè)趣，從中學(xué)到了不少知識(shí)， 雖然都說(shuō)“程序數(shù)據(jù)結(jié)構(gòu)算法”，但我們?cè)趯W(xué)習(xí)運(yùn)用數(shù)據(jù)結(jié)構(gòu)編程之

24、前，并沒(méi)能深刻體會(huì)到這一點(diǎn)，直到這次課設(shè)實(shí)踐。 我們感受最深的一點(diǎn)是：以前用C編程，只是注重如何編寫(xiě)函數(shù)能夠完成所需要的功能，似乎沒(méi)有明確的戰(zhàn)術(shù)，只是憑單純的意識(shí)和簡(jiǎn)單的語(yǔ)句來(lái)堆砌出一段程序。但現(xiàn)在編程感覺(jué)完全不同了。在編寫(xiě)一個(gè)程序之前，自己能夠綜合考慮各種因素，首先選取自己需要的數(shù)據(jù)結(jié)構(gòu)，然后選定一種或幾種存儲(chǔ)結(jié)構(gòu)來(lái)具體的決定后面的函數(shù)的主要風(fēng)格。最后在編寫(xiě)每一個(gè)函數(shù)之前，可以仔細(xì)斟酌比對(duì)，挑選出最適合當(dāng)前狀況的算法。這樣，即使在完整的還沒(méi)有寫(xiě)出來(lái)之前，自己心中已經(jīng)有了明確的原圖了。這樣無(wú)形中就提高了自己編寫(xiě)的程序的質(zhì)量。我們還體會(huì)到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性。只有真正理解定義數(shù)據(jù)類(lèi)型的好處，

25、才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu)的性質(zhì)是非常有用的，它往往是編寫(xiě)程序的關(guān)鍵。這次實(shí)驗(yàn)中我們也出現(xiàn)過(guò)一些錯(cuò)誤。但我們經(jīng)過(guò)反復(fù)調(diào)試后，發(fā)現(xiàn)并做了修改，從而完成了此次課程設(shè)計(jì)。 在這次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中，我此次的題目是各種排序，排序?qū)嶋H上是編程設(shè)計(jì)中應(yīng)用比較廣泛的知識(shí)，通過(guò)本次設(shè)計(jì)，我對(duì)一些基本的內(nèi)部排序有了很好的理解和掌握，并且通過(guò)此次課程設(shè)計(jì)中的程序運(yùn)行結(jié)果很好的理解了排序各種算法的穩(wěn)定性和時(shí)間復(fù)雜度，既鞏固了課堂上學(xué)到的排序理論，又為自己的編程增強(qiáng)了實(shí)踐?？傊谶@次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中，收獲還是蠻多的。也讓自己對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)課程有了更好的認(rèn)識(shí)，相信在越來(lái)越多的嘗試之后，自己會(huì)不斷

26、進(jìn)步不斷提高的。7. 參考文獻(xiàn)1.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 嚴(yán)蔚敏 清華大學(xué)出版社2.C語(yǔ)言程序設(shè)計(jì) 丁峻嶺 中國(guó)鐵道出版社3.C程序設(shè)計(jì) 譚浩強(qiáng) 清華大學(xué)出版社8. 附件程序源代碼：#include<cstdio>#include<algorithm>#include<iostream>#include<cmath>#include<cstring>#include<string>#include<stack>#include<map>#include<ctime>#include<

27、queue>#include<vector>#include<set>#include<cstdlib>using namespace std;const int N=;int data_num,data_arrayN,data_arrayyN;int oldN,aN,t;/數(shù)據(jù)輸入int input_num()printf("您要給多少個(gè)數(shù)排序？ntt");scanf("%d",&data_num);srand(NULL);printf("隨機(jī)產(chǎn)生%d個(gè)數(shù):ntt",data_num

28、);for(int i=1;i<=data_num;i+)data_arrayi=rand()%; printf("%dn",data_arrayi);oldi=data_arrayi; printf("ntt");/排序后數(shù)據(jù)輸出 從大到小 data_num 1int outnew0()printf("排序后的結(jié)果為:");for(int i=data_num;i>=1;i-)printf("%d%s",data_arrayi,i!=1?" ":"n");/排序

29、后逆序數(shù)據(jù)輸出 從小到大 1 data_numint outnew1()printf("排序后的結(jié)果為:");for(int i=1;i<=data_num;i+) printf("%d%s",data_arrayi,i!=data_num?" ":"n");/排序后數(shù)據(jù)輸出 從大到小 data_num-1 0int outnew2()printf("排序后的結(jié)果為:");for(int i=data_num-1;i>=0;i-)printf("%d%s",dat

30、a_arrayyi,i!=0?" ":"n");/排序后逆序數(shù)據(jù)輸出 從小到大 0 data_num-1int outnew3()printf("排序后的結(jié)果為:");for(int i=0;i<data_num;i+) printf("%d%s",data_arrayyi,i!=data_num-1?" ":"n");/插入排序void charu()int i,j;int temp; printf("插入排序:n");for(i=1;i<=

31、data_num;i+)int temp=data_arrayi;for (j=i;j>0 && temp<data_arrayj-1;j-)data_arrayj=data_arrayj-1;data_arrayj=temp;if(!t) outnew0();else outnew1();/冒泡排序void maopao()int temp;for(int i=1;i<=data_num;i+)for(int j=i+1;j<=data_num;j+)if(data_arrayi>data_arrayj)temp=data_arrayi;data

32、_arrayi=data_arrayj;data_arrayj=temp;/選擇排序void chose_sort(int a,int n)int min,temp;for(int i=0;i<n;i+)min=i;for(int j=i;j<n;j+)if(amin>aj)min=j;temp=amin; amin=ai;ai=temp;/堆排序void HeapAdjust(int *a,int i,int size)/調(diào)整堆 int lchild=2*i;/i的左孩子節(jié)點(diǎn)序號(hào) int rchild=2*i+1;/i的右孩子節(jié)點(diǎn)序號(hào) int max=i;/臨時(shí)變量 if(

33、i<=size/2)/如果i是葉節(jié)點(diǎn)就不用進(jìn)行調(diào)整 if(lchild<=size&&alchild>amax) max=lchild; if(rchild<=size&&archild>amax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size);/避免調(diào)整之后以max為父節(jié)點(diǎn)的子樹(shù)不是堆 void BuildHeap(int *a,int size)/建立堆 int i; for(i=size/2;i>=1;i-)/非葉節(jié)點(diǎn)最大序號(hào)值為size/2 H

34、eapAdjust(a,i,size);void HeapSort(int *a,int size)/堆排序 int j=1; BuildHeap(a,size); for(int i=size;i>=1;i-) swap(a1,ai); /交換堆頂和最后一個(gè)元素，即每次將剩余元素中的最大者放到最后面 /BuildHeap(a,i-1); /將余下元素重新建立為大頂堆 HeapAdjust(a,1,i-1); /重新調(diào)整堆頂節(jié)點(diǎn)成為大頂堆 /快速排序可以選擇用algorithm里的sort排序?qū)崿F(xiàn)void kuaisu1()/快速排序1 printf("快速排序:n"

35、); sort(data_array+1,data_array+data_num+1); if(!t) outnew0();else outnew1();void kuaisu2()/快速排序2 sort(data_array+1,data_array+data_num+1); if(!t) outnew0();else outnew1();/希爾排序void ShellInsert(int *a,int d,int n)for (int i=d;i<n;i+)/從第2個(gè)數(shù)據(jù)開(kāi)始插入int j=i-d;int temp=ai;/記錄要插入的數(shù)據(jù)while(j >= 0&&a

36、mp;aj>temp)/從后向前，找到比其小的數(shù)的位置aj+d=aj;/向后挪動(dòng)j-=d;if(j!=i-d)/存在比其小的數(shù)aj+d=temp;void ShellSort(int* a,int n)int d=n/2;/初始增量設(shè)為數(shù)組長(zhǎng)度的一半while(d>=1)ShellInsert(a,d,n);d=d/2;/每次增量變?yōu)樯洗蔚亩种?歸并排序void _merge(int a,int first,int mid,int last,int temp)int i=first,j=mid+1,m=mid,n=last,k=0;while(i<=m&&

37、j<=n)if(ai<=aj)tempk+=ai+;elsetempk+=aj+;while(i<=m)tempk+=ai+;while(j<=n)tempk+=aj+;for(i=0;i<k;i+)afirst+i=tempi;void MergeSort(int a,int first,int last,int temp) if(first<last) int mid=(first+last)/2; MergeSort(a,first,mid,temp); MergeSort(a,mid+1,last,temp); _merge(a,first,mid,

38、last,temp); bool MergeSort(int a,int n) int *p=new intn; if(p=NULL) return false; else MergeSort(a,0,n-1,p); delete p; return true; /輸出void print() printf("歡迎再次使用!nrn"); printf("*n"); printf("* . . . . . *n"); printf("* . . . . . . *n"); printf("* . . . .

39、 . . *n"); printf("* . . . . . . *n"); printf("* . . . . *n"); printf("*n");/主函數(shù)，顯示菜單并進(jìn)行算法選擇int main() printf("DATE:May twenty 2014n"); printf("All Copyright Reserved 2014-2015 Wang Guangchun n"); printf("ADDRESS: 604 AYITrnnn"); print

40、f(" n"); printf("各種排序比較 n"); printf("默認(rèn)從大到小輸出，可以選擇9進(jìn)行切換n"); printf(" n"); printf(" * * n"); printf(" * * * n"); printf(" * * n"); printf(" * 520 * n"); printf(" * 歡迎 * n"); printf(" * 使用 * n"); printf

41、(" * * n"); printf(" * n");int n;/變量定義用于菜單選擇input_num();/調(diào)用輸入函數(shù)，請(qǐng)求用戶輸入數(shù)據(jù)while(true)printf("n n");printf("請(qǐng)輸入指令 n");printf("* n");printf("$ 1.快速排序 $ n");printf("$ 2.歸并排序 $ n");printf("$ 3.堆排序 $ n");printf("$ 4.希爾排序 $

42、 n");printf("$ 5.插入排序 $ n");printf("$ 6.選擇排序 $ n");printf("$ 7.冒泡排序 $ n");printf("$ 8.重新隨機(jī)輸入 $ n");printf("$ 9.選擇排序方式 $ n");printf("* n");printf(" 0.退出 n");printf(" n");printf("請(qǐng)選擇：n");scanf("%d",&n);switch(n) case 1:/快速排序 kuaisu1();break; case 2:/歸并排序 printf("歸并排序：n"); for(int j=0;j<data_num;j+) data_arrayyj=data_