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

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

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

3、組表示集合數(shù)據(jù)類型。 int sN; int compare6=0,move6=0,DN=0,RSN=0;基本操作： 數(shù)組賦值：for(i=1;iN;i+) si=rand()%100; printf(%dt,si); void copys(int S,int RS,int n)/將s的值賦給RS,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)/快速排

4、序void QuickSortprint(int RS,int n)/輸出快速排序后的結(jié)果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)/將兩個(gè)有序序列歸并為一個(gè)有序序列void MSort(int RS,int low,int high)/歸并排序2. 主程序流程與其模塊調(diào)用關(guān)系 void SelectSort(int RS,int n) /直接選擇排序模塊void BubbleSort

5、(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)/將兩個(gè)有序序列歸并為一個(gè)有序序列模塊調(diào)用四、 詳細(xì)設(shè)計(jì) 1. 實(shí)現(xiàn)每個(gè)操作的偽碼，重點(diǎn)語句加注釋 1）void copys(int

6、 S,int RS,int n)/數(shù)組復(fù)制 int i; for(i=1;in;i+)RSi=Si;2） 直接選擇排序void SelectSort(int RS,int n) /直接選擇排序int i,j,k;for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)if(RSjRSk)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)鍵字的移動(dòng)

7、次數(shù)：%dn,compare0,move0);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+1RSj)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);printf(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)

8、鍵字的移動(dòng)次數(shù)：%dn,compare1,move1);printf(n);4） 直接插入排序void InsertSort(int RS,int n) /直接插入排序int i,j;for(i=2;i=n;i+)RS0=RSi;j=i-1;move2+;while(RS0RSj)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ù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare

9、2,move2);printf(n);5） 快速排序int QuickSort(int RS,int low,int high)/快速排序int i,j,n;n=high;i=low;j=high;RS0=RSi;move3+;while(i=RS0&ji)j-;compare3+;compare3+;if(ji)RSi=RSj;move3+;i+;while(RSii)i+;compare3+;compare3+; if(ji)RSj=RSi;move3+;j-;RSi=RS0;move3+;if(lowi)QuickSort(RS,low,i-1);if(ihigh)QuickSort(R

10、S,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(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare3,move3);printf(n);7） 一趟希爾排序，按間隔m劃分子序列void Shellsert(int RS,int m,int n)/一趟希爾排序，按間隔m劃分子序列int i,j,temp;for(

11、i=m;i=m&temp=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)鍵字的移動(dòng)次數(shù)：%dn,compare4,move4);printf(n);9） 將兩個(gè)有序序列歸并為一個(gè)有序序列void Merge(int RS,int low,int mid,int high)/將兩個(gè)有序序列歸并為一個(gè)有序序列int i,j,k;int n1,n2;i=low;j=mid+1;k=low

12、;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,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)/歸并排序i

13、nt mid;if(lowhigh)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 rawtime;struct tm * timeinfo; time (&rawtime);timeinfo = localtime (&rawtime); printf( 實(shí)驗(yàn)名稱：實(shí)驗(yàn)四：部排序算法的實(shí)現(xiàn)與比較n);printf( 學(xué)號：031350102n); printf( ：王亞文n); printf(=n);

14、printf(程序運(yùn)行開始，);printf(Current local time and date:%s,asctime(timeinfo);printf(產(chǎn)生的隨機(jī)數(shù)為：n); for(i=1;iN;i+) si=rand()%100; printf(%dt,si); printf(n); do copys(s,RS,N);printf(請選擇所需排序方法：); printf(n); printf(1.選擇法 ,2.冒泡法 ,3.插入法 ,4.快速法 , 5.希爾排序法 ,6.歸并排序法，7.輸出比較信息，8.退出n); scanf( %d,&j); switch(j) case 1: S

15、electSort(RS,N-1);break; case 2: BubbleSort(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;iN;i+)printf(%dt,Di);printf(n);printf(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare5,move5);prin

16、tf(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)鍵字的移動(dòng)次數(shù)：n);for(i=1;i=5;i+)printf(%dt,movei);printf(n);break;case 8: printf(Current local time and date:%s,asctime(timeinfo);exit(0);break; while(1); 五、 調(diào)試分析 1. 設(shè)計(jì)與調(diào)試

17、過程中遇到的問題分析、體會 調(diào)試過程：由于本次程序設(shè)計(jì)的數(shù)據(jù)和模塊比較多，所以采用分塊調(diào)試的方法，在編寫完一個(gè)部排序算法后，為了驗(yàn)證是否排序成功以與所輸出的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)是否正確，采用先定義一個(gè)需要排序9個(gè)數(shù)字的數(shù)組，S10=0，1，2，3，4，5，6，7，8，9和S10=0，9，8，7，6，5，4，3，2，1,用這兩個(gè)數(shù)組檢驗(yàn)程序的正確性與否。調(diào)試步驟，程序與相關(guān)結(jié)果如下：1） 直接選擇排序：#include #include #include void SelectSort(int RS,int n) /直接選擇排序int i,j,k,move=0,compare=0;for(i

18、=1;in;i+)k=i;for(j=i+1;j=n;j+)if(RSjRSk)k=j;compare+; if(k!=i) 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)鍵字的移動(dòng)次數(shù)：%dn,compare,move);printf(n);void main()int s10=0,1,2,3,4,5,6,7,8,9; SelectSort(s,9);s10=0,1,2,3,4,5,6,7,8,9;S1

19、0=0,9,8,7,6,5,4,3,2,12)冒泡排序#include #include #include #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+1RSj)flag=False;RS0=RSj;RSj=RSj+1;RSj+1=RS0;move+=3;compare+;if(flag=True)break;printf(冒泡排序后的結(jié)果：); for(i

20、=1;i=n;i+)printf(%dt,RSi);printf(n);printf(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare,move);printf(n);void main()int s10=0,1,2,3,4,5,6,7,8,9; BubbleSort(s,9);s10=0,1,2,3,4,5,6,7,8,9s10=0,9,8,7,6,5,4,3,2,1;3） 直接插入排序#include #include #include #define False 0#define True 1void InsertSort(int RS,int n) /直接插入排序i

21、nt i,j,compare=0,move=0;for(i=2;i=n;i+)RS0=RSi;j=i-1;move+;while(RS0RSj)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ù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare,move);printf(n);void main()int s10=0,9,8,7,6,5,4,3,2,1; InsertSort(s,9);

22、 s10=0,9,8,7,6,5,4,3,2,1;s10=0,1,2,3,4,5,6,7,8,9;4） 快速排序#include #include #include #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=RS0&ji)j-;compare3+;compare3+;if(ji)RSi=RSj;move3+;i+;while(RSii)i+;c

23、ompare3+;compare3+; if(ji)RSj=RSi;move3+;j-;RSi=RS0;move3+;if(lowi)QuickSort(RS,low,i-1);if(ihigh)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(n);printf(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare3,move3);p

24、rintf(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 #include #include #define False 0#define True 1int compare6=0,move6=0;void Shellsert(int RS,int m,int n)/一趟希爾排序，按間隔m劃分子序列int i,j,temp;for(i=m;i=m&temp=1)/循環(huán)直到m為0Shellsert(RS,m,n);m=(m=2?1:(m/

25、2);/縮小增進(jìn)量printf(希爾排序后的結(jié)果：); for(i=1;i=n;i+)printf(%dt,RSi);printf(n);printf(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare4,move4);printf(n);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 #include #include #define False 0#define True 1int c

26、ompare6=0,move6=0,D10=0;void Merge(int RS,int low,int mid,int high)/將兩個(gè)有序序列歸并為一個(gè)有序序列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,n2=j;n1=high&n2=

27、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(lowhigh)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(歸并排序后的結(jié)果：); for(i=1;i1

28、0;i+)printf(%dt,Di);printf(n);printf(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare5,move5);printf(n);s10=0,9,8,7,6,5,4,3,2,1；調(diào)試過程中遇到的問題：1）這個(gè)部排序算法的實(shí)現(xiàn)與比較程序設(shè)計(jì)中，大部分排序算法在書上已經(jīng)給了詳細(xì)的程序只需要稍加更改，所以在編寫排序程序時(shí)并沒有太大的問題，唯一的問題是for(mid=low;mid=high;mid+)RSmid=Dmid;move5+;這段程序一開始書上是放在MSort這個(gè)程序中，但是我放在這個(gè)程序里輸出的排序并不是按照升序排列的，將這段程序改在me

29、rge里，程序就能正常輸出了，還有一個(gè)問題是隨機(jī)數(shù)產(chǎn)生的數(shù)字是放在數(shù)組里的，執(zhí)行完第一個(gè)排序后再想去執(zhí)行下一個(gè)排序程序時(shí)再用原來的數(shù)組就已經(jīng)不是利用隨機(jī)函數(shù)產(chǎn)生的數(shù)組了而是經(jīng)過排序后形成的有序數(shù)組，這就影響了下一個(gè)程序的正常運(yùn)行，他所輸出的關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)就不是我們所想的隨機(jī)函數(shù)產(chǎn)生的數(shù)組排序時(shí)的比較次數(shù)和移動(dòng)次數(shù)，為了解決這個(gè)問題考慮另外定義一個(gè)數(shù)組，先利用隨機(jī)函數(shù)產(chǎn)生一個(gè)隨機(jī)數(shù)組，每次執(zhí)行排序前都將隨機(jī)數(shù)組中的數(shù)值賦給另一個(gè)數(shù)組，對另外的數(shù)組執(zhí)行排序程序，這就可以有效解決輸出的關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)不對的問題。這樣第一步顯示保證每個(gè)程序都可以將一個(gè)無序的序列排序成為有序序列。

30、2）在完成了第一步之后就可以進(jìn)行第二部，進(jìn)行關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的計(jì)算，一開始我是將每一個(gè)程序中都定義一個(gè)compare和move值，這種辦法在前幾個(gè)程序中并沒有什么問題，也沒有什么不方便，但在之后一個(gè)函數(shù)需要調(diào)用另一個(gè)函數(shù)時(shí)，因?yàn)橐粋€(gè)函數(shù)只能返回一個(gè)值，這個(gè)對于這個(gè)需要返回兩個(gè)值的程序就不適用了，所以就考慮定義了兩個(gè)數(shù)組，int compare6=0,move6=0，這樣就解決了這個(gè)不能再一個(gè)程序中返回兩個(gè)值得問題，同時(shí)也大大簡化了后面需要對各種部排序算法所產(chǎn)生的關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的排序與輸出，一舉兩得。這個(gè)程序是通過隨機(jī)數(shù)據(jù)產(chǎn)生N個(gè)隨機(jī)數(shù)，作為輸入數(shù)據(jù)作比較；對常用的部排序算

31、法：直接插入排序、簡單選擇排序、冒泡排序、快速排序、希爾排序、歸并排序進(jìn)行比較：比較的指標(biāo)為關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換記為3次移動(dòng)）。最后結(jié)果輸出各種排序算法的關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)，并按從小到大排列。6、 測試結(jié)果 7、 附錄 #include #include #include #include #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;in;i+)R

32、Si=Si;void SelectSort(int RS,int n) /直接選擇排序int i,j,k;for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)if(RSjRSk)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)鍵字的移動(dòng)次數(shù)：%dn,compare0,move0);printf(n);void BubbleSort(int

33、RS,int n)/冒泡排序int i,j,flag;for(i=1;i=n;i+)flag=True;for(j=1;j=n-i;j+)if(RSj+1RSj)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);printf(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare1,move1);printf(n);void InsertSort(int RS

34、,int n) /直接插入排序int i,j;for(i=2;i=n;i+)RS0=RSi;j=i-1;move2+;while(RS0RSj)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ù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare2,move2);printf(n);int QuickSort(int RS,int low,int high)/快速排序int i,j

35、,n;n=high;i=low;j=high;RS0=RSi;move3+;while(i=RS0&ji)j-;compare3+;compare3+;if(ji)RSi=RSj;move3+;i+;while(RSii)i+;compare3+;compare3+; if(ji)RSj=RSi;move3+;j-;RSi=RS0;move3+;if(lowi)QuickSort(RS,low,i-1);if(ihigh)QuickSort(RS,j+1,high);void QuickSortprint(int RS,int n)/輸出快速排序后的結(jié)果 int i;QuickSort(RS,

36、1,n);printf(快速排序后的結(jié)果：);for(i=1;i=n;i+)printf(%dt,RSi);printf(n);printf(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare3,move3);printf(n);void Shellsert(int RS,int m,int n)/一趟希爾排序，按間隔m劃分子序列int i,j,temp;for(i=m;i=m&temp=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,R

37、Si);printf(n);printf(關(guān)鍵字參加的比較次數(shù)：%d,關(guān)鍵字的移動(dòng)次數(shù)：%dn,compare4,move4);printf(n);void Merge(int RS,int low,int mid,int high)/將兩個(gè)有序序列歸并為一個(gè)有序序列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,n2=j;n1=high&n2=high;n1+,n2+)Dn1=RSn2;move5+; for(mid=low;mid=high;mid+)RSmid=Dm