文章目錄

• 1.思想
• • 1.1 思想流程圖
  • 1.2 思路解釋
• 2.算法執行過程
• 3.算法實現
• • 3.1 方法定義
  • 3.2 方法實現
  • 3.3 方法調用
• 4.復雜度

1.思想

1.1 思想流程圖

1.2 思路解釋

歸并排序思路:
1.總體思路:將待排序數組進行拆分成多個分組,然后將拆分后的分組有序的合并.
2.現將數組拆分成分組長度(length=1)最小分組.然后將相鄰分組兩兩進行有序合并.
2.1 如果總的分組數為偶數,那么正好兩兩合并.
2.2 如果總的分組數為奇數,那么剩下的單個的直接拼在新數組的后面即可.
2.3.生成一個按照長度為length合并后的新數組.
3.將新的數組進行第二步的操作(length=length*2).直到length>=待排序數組的長度,那么歸并結束.也就是最新的歸并的數組中只有一個分組,并且是排序好的數組.

2.算法執行過程

歸并前數組:3,7,4,2,8,6,10,11,5,1 -------------開始歸并:分組長度:length:1------------ 待合并分組1角標范圍:[0~0],下面是角標范圍內的值: 3 待合并分組2角標范圍:[1~1],下面是角標范圍內的值: 7 分組合并的有序結果:3,7 待合并分組1角標范圍:[2~2],下面是角標范圍內的值: 4 待合并分組2角標范圍:[3~3],下面是角標范圍內的值: 2 分組合并的有序結果:2,4 待合并分組1角標范圍:[4~4],下面是角標范圍內的值: 8 待合并分組2角標范圍:[5~5],下面是角標范圍內的值: 6 分組合并的有序結果:6,8 待合并分組1角標范圍:[6~6],下面是角標范圍內的值: 10 待合并分組2角標范圍:[7~7],下面是角標范圍內的值: 11 分組合并的有序結果:10,11 待合并分組1角標范圍:[8~8],下面是角標范圍內的值: 5 待合并分組2角標范圍:[9~9],下面是角標范圍內的值: 1 分組合并的有序結果:1,5 -------------該此歸并結束:分組長度:length:1------------- 3,7,2,4,6,8,10,11,1,5 -------------開始歸并:分組長度:length:2------------ 待合并分組1角標范圍:[0~1],下面是角標范圍內的值: 3,7 待合并分組2角標范圍:[2~3],下面是角標范圍內的值: 2,4 分組合并的有序結果:2,3,4,7 待合并分組1角標范圍:[4~5],下面是角標范圍內的值: 6,8 待合并分組2角標范圍:[6~7],下面是角標范圍內的值: 10,11 分組合并的有序結果:6,8,10,11 待合并分組1角標范圍:[8~9],下面是角標范圍內的值: 1,5 分組合并的有序結果:1,5 -------------該此歸并結束:分組長度:length:2------------- 2,3,4,7,6,8,10,11,1,5 -------------開始歸并:分組長度:length:4------------ 待合并分組1角標范圍:[0~3],下面是角標范圍內的值: 2,3,4,7 待合并分組2角標范圍:[4~7],下面是角標范圍內的值: 6,8,10,11 分組合并的有序結果:2,3,4,6,7,8,10,11 待合并分組1角標范圍:[8~9],下面是角標范圍內的值: 1,5 分組合并的有序結果:1,5 -------------該此歸并結束:分組長度:length:4------------- 2,3,4,6,7,8,10,11,1,5 -------------開始歸并:分組長度:length:8------------ 待合并分組1角標范圍:[0~7],下面是角標范圍內的值: 2,3,4,6,7,8,10,11 待合并分組2角標范圍:[8~9],下面是角標范圍內的值: 1,5 分組合并的有序結果:1,2,3,4,5,6,7,8,10,11 -------------該此歸并結束:分組長度:length:8------------- 1,2,3,4,5,6,7,8,10,11 總的歸并結束,數組:1,2,3,4,5,6,7,8,10,11

3.算法實現

3.1 方法定義

mergeGroup:相鄰放個分組合并
mergePassByLength:數組中指定分組長度,將所有分組進行合并,稱為一次歸并
mergeArray:歸并算法
printArray:打印數組,為了查看算法執行過程

#define SIZE 10 /*數組中的指定兩個分組合并將原來數組中的通過兩個位置分成的數組有序合并到一個新的數組中對應的位置oArray: [oStartPosition,oMiddlePosition],[oMiddlePosition+1,oEndPosition]oArray:待排序的數組oStartPosition:第一個組的其實位置oMiddlePosition:第一個組的結束位置oEndPosition:第二個組的結束位置*/ void mergeGroup(int oArray[],int oStartPosition,int oMiddlePosition,int oEndPosition,int nArray[]); /*按照指定分組長度,進行一次歸并一般:長度為1,長度為2,...長度為n.當長度為n時,說明歸并的結果就是一個整個有序的數組oArray:待歸并的數組nArray:歸并后的數組groupLength:分組的長度*/ void mergePassByLength(int oArray[],int nArray[],int groupLength); /*歸并排序,將指定數組進行歸并排序oArray:待排序數組這里為了方便,將數組長度定義為了全局的:SIZE=10*/ void mergeArray(int oArray[]); //打印數組 void printArray(int array[],int start,int end);

3.2 方法實現

void mergeGroup(int oArray[],int oStartPosition,int oMiddlePosition,int oEndPosition,int nArray[]){//1.oArray的分組//[oStartPosition,oMiddlePosition],//[oMiddlePosition+1,oEndPosition]printf("待合并分組1角標范圍:[%d~%d],下面是角標范圍內的值:\n",oStartPosition,oMiddlePosition);printArray(oArray,oStartPosition,oMiddlePosition);if(oMiddlePosition+1<=oEndPosition){printf("待合并分組2角標范圍:[%d~%d],下面是角標范圍內的值:\n",oMiddlePosition+1,oEndPosition);printArray(oArray,oMiddlePosition+1,oEndPosition);}int i=oStartPosition;int j=oMiddlePosition+1;int k=oStartPosition;//2.遍歷兩個分組while (i<=oMiddlePosition && j<=oEndPosition) {if(oArray[i]<oArray[j]){nArray[k++]=oArray[i];i++;}else{nArray[k++]=oArray[j];j++;}}//3.只會剩下一個分組有數據//如果第一個分組剩下數組,新數組后面.如果第二個分組剩下數組,新數組后面while(i<=oMiddlePosition){nArray[k++]=oArray[i++];}while(j<=oEndPosition){nArray[k++]=oArray[j++];}//4.合并結束.有序合并到了nArray的[oStartPosition,oEndPosition]printf("分組合并的有序結果:");printArray(nArray, oStartPosition,oEndPosition); }void mergePassByLength(int oArray[],int nArray[],int groupLength){int start;int middle;int end;//按照分組長度進行合并printf("-------------開始歸并:分組長度:length:%d------------\n",groupLength);for(int i=0;i<SIZE;i=i+2*groupLength){start=i;middle=i+groupLength-1;end=i+2*groupLength-1;if(middle>=SIZE){middle=SIZE-1;}if(end>=SIZE){end=SIZE-1;}mergeGroup(oArray, start,middle, end, nArray);}printf("-------------該此歸并結束:分組長度:length:%d-------------\n",groupLength);printArray(nArray,0,9); }void mergeArray(int oArray[]){printf("歸并前數組:");printArray(oArray, 0, 9);int nArray[SIZE];int length=1;int flag=1;while (length<SIZE) {//這里待歸并和歸并數組進行替換,復用.if(flag==1){//oArray:是待歸并數組,nArray:歸并后數組.oArray->nArray 進行歸并mergePassByLength(oArray,nArray,length);flag=0;}else{mergePassByLength(nArray,oArray,length);flag=1;}length=length*2;}printf("總的歸并結束,數組:");if(flag==0){printArray(nArray, 0, 9);}else{printArray(oArray, 0, 9);} }void printArray(int array[],int start,int end){for(int i=start;i<=end;i++){if(i==start){printf("%d",array[i]);}else{printf(",%d",array[i]);}}printf("\n"); }

3.3 方法調用

int main(int argc, const char * argv[]) {int oArray[]={3,7,4,2,8,6,10,11,5,1};mergeArray(oArray);return 0; }

4.復雜度

時間復雜度:O(n${\log }_{2}n$)
控件復雜度:O(n),因為創建了一個新數組和待排序數組進行交替歸并.

源碼下載

總結

以上是生活随笔為你收集整理的排序:归并排序(C)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。