對n個元素進行排序，n個元素可以看成n個長度為1的有序子數(shù)列。

兩兩合并，可以得到個長度為2或1的有序子數(shù)列。

再兩兩合并，如此反復，最終得到長度為n的有序數(shù)列。

?

主要函數(shù)有2個

Merge，將前后兩個相鄰的有序數(shù)列合并為一個有序數(shù)列。

假設(shè)在數(shù)列A中存在兩段相鄰的有序數(shù)列，A[low...mid], A[mid+1...high]，先將它們復制到臨時數(shù)組B中，然后每次從B中取出這兩段有序數(shù)列的頭部元素進行大小比較，將較小的放入A中，并向后移動該段有序數(shù)列的頭部位置，當這兩段有序數(shù)列中的其中一個頭部位置已經(jīng)超過了其末尾之時，將另一段有序數(shù)列剩余的部分直接復制到A余下的位置上即可。

int *B= (int *)malloc(n*sizeof(int)); void Merge(int A[],int low, int mid, int high){for(int k=low;k<=high;k++)B[k]=A[k]; //將A中元素全部復制到臨時數(shù)組B中for(i=low, j=mid+1,k=i;i<=mid && j<=high;k++){if(B[i]<=B[j]) //比較臨時數(shù)組B中原來兩段有序數(shù)列的頭部元素大小A[k]=B[i++]; //將較小的放回A中elseA[k]=B[j++];}while(i<=mid)A[k++]=B[i++]; //如果第一段數(shù)列未檢測完，復制剩余部分while(j<=high)A[k++]=B[j++]; //同理第二段 }

代碼中兩個while最終只會運行一個。

然后是MergeSort

void MergeSort(int A[], int low, int high){if(low<high){int mid=(low+high)/2; //從中劃分兩個子數(shù)列MergeSort(A,low,mid); //對左側(cè)進行遞歸排序MergeSort(A,mid+1,high); //右側(cè)同理Merge(A,low,mid,high); //合并左右結(jié)果} }

?

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。