內(nèi)部排序算法的實現(xiàn)與比較

1、實驗四：內(nèi)部排序算法的實現(xiàn)與比較1、 問題描述1 實驗題目：在教科書中，各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大致執(zhí)行時間。試通過隨機數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。2 基本要求：( 1)對常用的內(nèi)部排序算法進(jìn)行比較：直接插入排序、簡單選擇排序、冒泡排序、快速排序、希爾排序、歸并排序。(2利用隨機函數(shù)產(chǎn)生N (N=30000)個隨機整數(shù)，作為輸入數(shù)據(jù)作比較；比較的指標(biāo)為關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)(關(guān)鍵字交換記為3 次移動) 。( 3) 對結(jié)果作出簡要分析。3 測試數(shù)據(jù)：隨機函數(shù)產(chǎn)生。2、 需求分析1 程序所能達(dá)到的基本可能：

2、通過隨機數(shù)據(jù)產(chǎn)生N 個隨機數(shù)，作為輸入數(shù)據(jù)作比較；對常用的內(nèi)部排序算法：直接插入排序、簡單選擇排序、冒泡排序、快速排序、希爾排序、歸并排序進(jìn)行比較：比較的指標(biāo)為關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)(關(guān)鍵字交換記為3 次移動) 。最后結(jié)果輸出各種排序算法的關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)，并按從小到大排列。2 .輸入的形式及輸入值范圍：隨機函數(shù)產(chǎn)生的 N (N=30000)個隨機整數(shù)。3 輸出的形式：輸出各種排序算法的關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)。并按從小到大排列。4 .測試數(shù)據(jù)要求：隨機函數(shù)產(chǎn)生的N (N=30000)個隨機整數(shù)。3、 概要設(shè)計1. 所用到得數(shù)據(jù)結(jié)構(gòu)及其ADT

3、為了實現(xiàn)上述功能，應(yīng)以一維數(shù)組表示集合數(shù)據(jù)類型。int sN;int compare6=0,move6=0,DN=0,RSN=0;基本操作：數(shù)組賦值：for(i=1;i<N;i+) void copys(int S,int RS,int n)/void SelectSort(int RS,int n) / void BubbleSort(int RS,int n)/ void InsertSort(int RS,int n) / int QuickSort(int RS,int low,int high)/ void QuickSortprint(int RS,int n)/ void

4、Shellsert(int RS,int m,int n)/ void Shellsort(int RS,int n)/si=rand()%100;printf("%dt",si);將 s 的值賦給RS,直接選擇排序冒泡排序直接插入排序快速排序輸出快速排序后的結(jié)果一趟希爾排序，按間隔m劃分子序列希爾排序void Merge(int RS,int low,int mid,int high)/將兩個有序序列歸并為一個有序序列void MSort(int RS,int low,int high)/歸并排序2. 主程序流程及其模塊調(diào)用關(guān)系void SelectSort(int RS

5、,int n) /直接選擇排序模塊開始冒泡排序模塊void BubbleSort(int RS,int n)/void InsertSort(int RS,int n) /直接插入排序模塊int QuickSort(int RS,int low,int high)/快速排序模塊void Shellsert(int RS,int m,int n)/一趟希爾排序，按間隔m劃分子序列void Shellsort(int RS,int n)/希爾排序模塊void Merge(int RS口,int low,int mid,int high)/將兩個有序序列歸并為一個有序序列開始結(jié)束模塊調(diào)用void S

6、electSort(int RS,intn) /直接選擇排序void InsertSort(intRS,intn) /直接插入排序void copys(int S,int RS,int n)將s口的值賦給RS口，voidBubbleSort(intRS,intn)/冒泡排序voidQuickSortprint(intRS,int n)/快速排序后的結(jié)果intQuickSort(intRS,intlow,int high)/快速排序Shellsort(RS,N-1);希爾排序-AvoidShellsert(intRS,intm,int n)/一趟希爾排序，按間隔 m劃分子序列MSort(RS,1

7、,N-1); 歸并排序>Merge(RS,low,mid,high);將兩個有序序列歸并為一個有序序列四、詳細(xì)設(shè)計1 .實現(xiàn)每個操作的偽碼，重點語句加注釋1) void copys(int S,int RS,int n)/數(shù)組復(fù)制int i;for(i=1;i<n;i+)RSi=Si;2)直接選擇排序void SelectSort(int RS,int n) /直接選擇排序int i,j,k;for(i=1;i<n;i+) k=i;for(j=i+1;j<=n;j+) if(RSj<RSk)k=j;compare0+;if(k!=i)RS0=RSk;RSk=RSi

8、;RSi=RS0;move0+=3;printf(" 直接選擇排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù):printf("n");3)冒泡排序void BubbleSort(int RS,int n)/冒泡排序int i,j,flag;for(i=1;i<=n;i+)flag=True;for(j=1;j<=n-i;j+)if(RSj+1<RSj)flag

9、=False;RS0=RSj;RSj=RSj+1;RSj+1=RS0;move1+=3;compare1+;if(flag=True) break;printf(" 冒泡排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù):printf("n");%dn",compare0,move0);%dn",compare1,move1);4)直接插入排序void Inse

10、rtSort(int RS,int n) /直接插入排序int i,j;for(i=2;i<=n;i+)RS0=RSi;j=i-1;move2+;while(RS0<RSj) 5）快速排序compare2+;RSj+1=RSj; move2+; j-;compare2+;RSj+1=RS0; move2+; printf(" 直接插入排序后的結(jié)果：for(i=1;i<=n;i+) printf("%dt",RSi); printf("n");printf(" 關(guān)鍵字參加的比較次數(shù)： printf("n&qu

11、ot;);快速排序");%d,關(guān)鍵字的移動次數(shù):%dn",compare2,move2);快速排序int QuickSort(int RS,int low,int high)/ int i,j,n;n=high;i=low;j=high;RS0=RSi;move3+;while(i<j)while(RSj>=RS0&&j>i)j-;compare3+;compare3+;if(j>i)RSi=RSj;move3+;i+;while(RSi<=RS0&&j>i)i+;compare3+;compare3+;i

12、f(j>i)RSj=RSi;move3+;j-;RSi=RS0;move3+;if(low<i)QuickSort(RS,low,i-1);if(i<high)QuickSort(RS,j+1,high);6)輸出快速排序后的結(jié)果void QuickSortprint(int RS,int n)/輸出快速排序后的結(jié)果 int i;QuickSort(RS,1,n);printf(" 快速排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf(

13、"關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù)：dn",compare3,move3);printf("n");7) 一趟希爾排序，按間隔m劃分子序列void Shellsert(int RS口,int m,int n)一趟希爾排序，按間隔m劃分子序列int i,j,temp;for(i=m;i<=n/m;i+)temp=RSi;j=i;while(j>=m&&temp<RSj-m)compare4+;RSj=RSj-m;move4+;j-=m; RSj=temp; move4+; 8)希爾排序void Shellsort

14、(int RS,int n)/希爾排序int m,i;m=n/2;while(m>=1)/ 循環(huán)直到m為0 Shellsert(RS,m,n);m=(m=2?1:(m/2);/ 縮小增進(jìn)量printf(" 希爾排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù)：dn",compare4,move4);printf("n");9)將兩個有序序列歸并為一個有序序列voi

15、d Merge(int RS,int low,int mid,int high)/將兩個有序序列歸并為一個有序序列int i,j,k;int n1,n2;i=low;j=mid+1;k=low;while(i<=mid&&j<=high)/ 兩兩比較 if(RSi<=RSj) Dk=RSi;i+;k+; else Dk=RSj;j+;k+;compare5+;move5+;if(i<=mid)for(n1=k,n2=i;n1<=high&&n2<=mid;n1+,n2+)Dn1=RSn2;move5+;elsefor(n1=k

16、,n2=j;n1<=high&&n2<=high;n1+,n2+) Dn1=RSn2;move5+;for(mid=low;mid<=high;mid+)RSmid=Dmid;move5+;10)歸并排序void MSort(int RS,int low,int high)/歸并排序int mid;if(low<high)mid=(low+high)/2;MSort(RS,low, mid);MSort(RS, mid+1,high);Merge(RS,low,mid,high);11)主函數(shù)void main()int i,j,sN;time_t ra

17、wtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);n");printf("實驗名稱：實驗四：內(nèi)部排序算法的實現(xiàn)與比較printf("姓名：王亞文n");printf("=n");printf(" 程序運行開始，");printf("Current local time and date:%s",asctime(timeinfo);printf(" 產(chǎn)生的隨機數(shù)為：n&qu

18、ot;);for(i=1;i<N;i+)si=rand()%100;printf("%dt",si);printf("n");docopys(s,RS,N);printf(" 請選擇所需排序方法：");printf("n");printf("1. 選擇法 ,2. 冒泡法 ,3. 插入法輸出比較信息，8. 退出 n");scanf(" %d",&j);switch(j)case 1:SelectSort(RS,N-1);break;case 2:BubbleSor

19、t(RS,N-1);break;case 3:InsertSort(RS,N-1);break;case 4:QuickSortprint(RS,N-1);break;case 5:Shellsort(RS,N-1);break;case 6:MSort(RS,1,N-1);printf(" 歸并排序后的結(jié)果：");for(i=1;i<N;i+)printf("%dt",Di);printf("n");printf(" 關(guān) 鍵 字 參 加 的數(shù)： %dn",compare5,move5);printf(&qu

20、ot;n");,4. 快速法 , 5. 希爾排序法,6. 歸并排序法，7.較 次 數(shù) ：%d, 關(guān) 鍵 字 的 移 動 次break;case 7:SelectSort(compare,5);SelectSort(move,5);printf(" 關(guān)鍵字參加的比較次數(shù):n");for(i=1;i<=5;i+)printf("%dt",comparei);printf("n");printf(" 關(guān)鍵字的移動次數(shù)：n");for(i=1;i<=5;i+)printf("%dt"

21、;,movei);printf("n"); break;case 8:printf("Current local time and date:%s",asctime(timeinfo);exit(0); break; while(1);五、 調(diào)試分析1. 設(shè)計與調(diào)試過程中遇到的問題分析、體會調(diào)試過程：由于本次程序設(shè)計的數(shù)據(jù)和模塊比較多，所以采用分塊調(diào)試的方法，在編寫完一個內(nèi)部排序算法后，為了驗證是否排序成功以及所輸出的關(guān)鍵字比較次數(shù)和移動次數(shù)是否正確，采用先定義一個需要排序9 個數(shù)字的數(shù)組，S10=0 ， 1， 2， 3， 4， 5， 6， 7， 8，

22、9和 S10=0 ， 9， 8， 7， 6， 5，4， 3， 2， 1, 用這兩個數(shù)組檢驗程序的正確性與否。調(diào)試步驟，程序及相關(guān)結(jié)果如下：1 )直接選擇排序：#include <stdio.h>#include <malloc.h>#include <stdlib.h>void SelectSort(int RS,int n) /直接選擇排序int i,j,k,move=0,compare=0; for(i=1;i<n;i+) k=i;for(j=i+1;j<=n;j+) if(RSj<RSk) k=j;compare+; if(k!=i)

23、 RS0=RSk;RSk=RSi;RSi=RS0;move+=3;printf(" 直接選擇排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù)：dn",compare,move);printf("n");void main()int s10=0,12345,6,7,8,9;SelectSort(s,9);s10=0,123,4,5,6,7,8,9;接選擇排序后的結(jié)果：1

24、23 i 5678（鍵字參加的比較次數(shù)：孤,關(guān)鍵字的移前就數(shù)，0S10=0,9,8,7,6,5,4,3,2,12)冒泡排序#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define False 0#define True 1void BubbleSort(int RS口,int n)/冒泡排序int i,j,flag,move=0,compare=0; for(i=1;i<=n;i+) flag=True;for(j=1;j<=n-i;j+)if(RSj+1<RSj)fla

25、g=False;RS0=RSj;RSj=RSj+1;RSj+1=RS0;move+=3; compare+;if(flag=True) break;printf(" 冒泡排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù)：dn",compare,move);printf("n");void main()int s10=0,12345,6,7,8,9;BubbleSort(

26、s,9);s10=0,123,4,5,6,7,8,9冒泡排序后的菇果，i245 ft 7、鍵字多加的比線次數(shù)：心關(guān)犍？蝴綠欣戮：0s10=0,9,8,7,6,5,4,3,2,1;3)直接插入排序#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define False 0#define True 1void InsertSort(int RS,int n) /直接插入排序int i,j,compare=0,move=0;for(i=2;i<=n;i+) RS0=RSi; j=i-1; mo

27、ve+;while(RS0<RSj) compare+; RSj+1=RSj; move+; j-; compare+;RSj+1=RS0;move+;printf(" 直接插入排序后的結(jié)果：for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf(" 關(guān)鍵字參加的比較次數(shù)：printf("n");");%d,關(guān)鍵字的移動次數(shù):%dn",compare,move);void main()int s10=0,9,8,7,6,5,4,3,2

28、,1;InsertSort(s,9);s10=0,9,8,7,6,5,4,3,2,1;s10=0,1,2,3,4,5,6,7,8,9;4)快速排序#include <stdio.h>#include <malloc.h> #include <stdlib.h>#define False 0 #define True 1int compare6=0,move6=0;快速排序int QuickSort(int RS,int low,int high)/int i,j,n;n=high;i=low;j=high;RS0=RSi;move3+;while(i<

29、j)while(RSj>=RS0&&j>i)j-;compare3+;compare3+;if(j>i)RSi=RSj;move3+;i+;while(RSi<=RS0&&j>i)i+;compare3+;compare3+;if(j>i)RSj=RSi;move3+;j-;RSi=RS0;move3+;if(low<i)QuickSort(RS,low,i-1);if(i<high)QuickSort(RS,j+1,high);void QuickSortprint(int RS,int n)/ int i;Qu

30、ickSort(RS,1,n);printf(" 快速排序后的結(jié)果：for(i=1;i<=n;i+) printf("%dt",RSi);printf("n");");輸出快速排序后的結(jié)果printf(" 關(guān)鍵字參加的比較次數(shù)：printf("n");void main()int s10=0,9,8,7,6,5,4,3,2,1;QuickSortprint(s,9);s10=0,9,8,7,6,5,4,3,2,1;5)希爾排序#include <stdio.h>%d,關(guān)鍵字的移動次數(shù)：d

31、n",compare3,move3);#include <malloc.h>#include <stdlib.h>#define False 0#define True 1int compare6=0,move6=0;void Shellsert(int RS,int m,int n)/ int i,j,temp;for(i=m;i<=n/m;i+)一趟希爾排序，按間隔 m劃分子序列temp=RSi;j=i;while(j>=m&&temp<RSj-m)compare4+;RSj=RSj-m;move4+;j-=m;RSj=t

32、emp;move4+;void Shellsort(int RS,int n)/希爾排序int m,i;m=n/2;while(m>=1)/ 循環(huán)直到m為0Shellsert(RS,m,n);m=(m=2?1:(m/2);/ 縮小增進(jìn)量printf(" 希爾排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù)：dn",compare4,move4);printf("n"

33、;);void main() int s10=0,9,8,7,6,5,4,3,2,1;Shellsort(s,9);s10=0,9,8,7,6,5,4,3,2,1;s10=0,1,2,3,4,5,6,7,8,9;6)歸并排序#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define False 0#define True 1int compare6=0,move6=0,D10=0;將兩個有序序列歸并為一個有序序列void Merge(int RS,int low,int mid,int hi

34、gh)/int i,j,k; int n1,n2; i=low; j=mid+1; k=low; while(i<=mid&&j<=high)/兩兩比較( if(RSi<=RSj) ( Dk=RSi; i+; k+; else (Dk=RSj; j+; k+; compare5+; move5+; if(i<=mid) for(n1=k,n2=i;n1<=high&&n2<=mid;n1+,n2+) ( Dn1=RSn2; move5+; else for(n1=k,n2=j;n1<=high&&n2&l

35、t;=high;n1+,n2+) ( Dn1=RSn2; move5+; for(mid=low;mid<=high;mid+) ( RSmid=Dmid; move5+; void MSort(int RS,int low,int high)/歸并排序( int mid; if(low<high)mid=(low+high)/2;MSort(RS,low, mid);MSort(RS, mid+1,high);Merge(RS,low,mid,high);void main()int s10=0,9,8,7,6,5,4,3,2,1,i;MSort(s,1,9);printf(&q

36、uot; 歸并排序后的結(jié)果：");for(i=1;i<10;i+)printf("%dt",Di);printf("n");printf(" 關(guān) 鍵 字 參 加 的 比 較 次 數(shù) ：%d, 關(guān) 鍵 字 的 移 動 次數(shù)： %dn",compare5,move5);printf("n");s10=0,9,8,7,6,5,4,3,2,1；調(diào)試過程中遇到的問題：1 )這個內(nèi)部排序算法的實現(xiàn)與比較程序設(shè)計中，大部分排序算法在書上已經(jīng)給了詳細(xì)的程序只需要稍加更改，所以在編寫排序程序時并沒有太大的問題，唯一的

37、問題是for(mid=low;mid<=high;mid+)RSmid=Dmid;move5+;這段程序一開始書上是放在MSort 這個程序中，但是我放在這個程序里輸出的排序并不是按照升序排列的，將這段程序改在merge 里，程序就能正常輸出了，還有一個問題是隨機數(shù)產(chǎn)生的數(shù)字是放在數(shù)組里的， 執(zhí)行完第一個排序后再想去執(zhí)行下一個排序程序時再用原來的數(shù)組就已經(jīng)不是利用隨機函數(shù)產(chǎn)生的數(shù)組了而是經(jīng)過排序后形成的有序數(shù)組，這就影響了下一個程序的正常運行，他所輸出的關(guān)鍵字的比較次數(shù)和移動次數(shù)就不是我們所想的隨機函數(shù)產(chǎn)生的數(shù)組排序時的比較次數(shù)和移動次數(shù)，為了解決這個問題考慮另外定義一個數(shù)組，先利用隨機

38、函數(shù)產(chǎn)生一個隨機數(shù)組，每次執(zhí)行排序前都將隨機數(shù)組中的數(shù)值賦給另一個數(shù)組，對另外的數(shù)組執(zhí)行排序程序，這就可以有效解決輸出的關(guān)鍵字的比較次數(shù)和移動次數(shù)不對的問題。這樣第一步顯示保證每個程序都可以將一個無序的序列排序成為有序序列。2)在完成了第一步之后就可以進(jìn)行第二部，進(jìn)行關(guān)鍵字的比較次數(shù)和移動次數(shù)的計算，一開始我是將每一個程序中都定義一個compare和move值，這種辦法在前幾個程序中并沒有什么問題，也沒有什么不方便，但在之后一個函數(shù)需要調(diào)用另一個函數(shù)時，因為一個函數(shù)只能返回一個值，這個對于這個 需 要 返 回 兩 個 值 的 程 序 就 不 適 用 了 ， 所 以 就 考 慮 定 義 了 兩

39、個 數(shù) 組 ， intcompare6=0,move6=0， 這樣就解決了這個不能再一個程序中返回兩個值得問題，同時也大大簡化了后面需要對各種內(nèi)部排序算法所產(chǎn)生的關(guān)鍵字的比較次數(shù)和移動次數(shù)的排序與輸出，一舉兩得。這個程序是通過隨機數(shù)據(jù)產(chǎn)生N 個隨機數(shù)，作為輸入數(shù)據(jù)作比較；對常用的內(nèi)部排序算法：直接插入排序、簡單選擇排序、冒泡排序、快速排序、希爾排序、歸并排序進(jìn)行比較：比較的指標(biāo)為關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)(關(guān)鍵字交換記為3 次移動) 。最后結(jié)果輸出各種排序算法的關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)，并按從小到大排列。六、測試結(jié)果七、附錄#include <stdio.h&g

40、t;#include <malloc.h>#include <stdlib.h>#include <time.h>#define N 100#define False 0#define True 1int compare6=0,move6=0,DN=0,RSN=0;void copys(int S,int RS,int n)int i;for(i=1;i<n;i+)RSi=Si;void SelectSort(int RS,int n) /直接選擇排序int i,j,k;for(i=1;i<n;i+)k=i;for(j=i+1;j<=n;j

41、+)if(RSj<RSk)k=j;compare0+;if(k!=i)RS0=RSk;RSk=RSi;RSi=RS0;move0+=3;printf(" 直接選擇排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù)：dn",compare0,move0);printf("n");void BubbleSort(int RS,int n)/冒泡排序int i,j,fla

42、g;for(i=1;i<=n;i+) flag=True;for(j=1;j<=n-i;j+)if(RSj+1<RSj)flag=False;RS0=RSj;RSj=RSj+1;RSj+1=RS0;move1+=3; compare1+; if(flag=True) break; printf(" 冒泡排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");%dn",compare1,move1);printf(" 關(guān)鍵字參加的比較次數(shù)

43、：d,關(guān)鍵字的移動次數(shù):printf("n");void InsertSort(int RS,int n) /直接插入排序int i,j;for(i=2;i<=n;i+) RS0=RSi;j=i-1;move2+;while(RS0<RSj) compare2+; RSj+1=RSj; move2+; j-;compare2+;RSj+1=RS0;move2+;printf(" 直接插入排序后的結(jié)果：for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf(&

44、quot; 關(guān)鍵字參加的比較次數(shù)： printf("n");int QuickSort(int RS,int low,int high)/int i,j,n;n=high;i=low;j=high;RS0=RSi;move3+;while(i<j)while(RSj>=RS0&&j>i)j-;compare3+;compare3+;if(j>i)RSi=RSj;move3+; i+;while(RSi<=RS0&&j>i)");%d,關(guān)鍵字的移動次數(shù):快速排序%dn",compare2,

45、move2);i+;compare3+;compare3+;if(j>i)RSj=RSi;move3+;j-;RSi=RS0;move3+;if(low<i)QuickSort(RS,low,i-1);if(i<high)QuickSort(RS,j+1,high);void QuickSortprint(int RS,int n)/輸出快速排序后的結(jié)果 int i;QuickSort(RS,1,n);printf(" 快速排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf(&qu

46、ot;n");printf("關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù)：dn",compare3,move3);printf("n");void Shellsert(int RS口,int m,int n)一趟希爾排序，按間隔m劃分子序列int i,j,temp;for(i=m;i<=n/m;i+)temp=RSi;j=i;while(j>=m&&temp<RSj-m)compare4+;RSj=RSj-m;move4+;j-=m;RSj=temp;move4+;void Shellsort(int RS,i

47、nt n)/希爾排序int m,i;m=n/2;while(m>=1)/ 循環(huán)直到m為0Shellsert(RS,m,n);m=(m=2?1:(m/2);/ 縮小增進(jìn)量printf(" 希爾排序后的結(jié)果：");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n"); printf("關(guān)鍵字參加的比較次數(shù)：d,關(guān)鍵字的移動次數(shù)：%dn",compare4,move4);printf("n");) void Merge(int RS口,int low,

48、int mid,int high)/將兩個有序序列歸并為一個有序序列(int i,j,k; int n1,n2; i=low; j=mid+1; k=low; while(i<=mid&&j<=high)/兩兩比較( if(RSi<=RSj) ( Dk=RSi; i+; k+; ) else ( Dk=RSj; j+; k+; ) compare5+; move5+;) if(i<=mid) for(n1=k,n2=i;n1<=high&&n2<=mid;n1+,n2+) ( Dn1=RSn2; move5+; ) else for(n1=k,n2=j;n1<=high&&n2<=hig