其基本模式如下：

分解：把一個問題分解成與原問題相似的子問題

解決：遞歸的解各個子問題

合并：合并子問題的結(jié)果得到了原問題的解。

現(xiàn)在就用遞歸算法，采用上面的分治思想來解合并排序。

合并排序（非降序）

分解：把合并排序分解成與兩個子問題

偽代碼：

MERGE_SORT(A, begin, end) 
if begin < end 
   then mid<- int((begin + end)/2) 
           MERGE_SORT(A, begin, mid) 
           MERGE_SORT(A, mid+1, end) 
           MERGE(A, begin, mid, end) 

解決：遞歸的解各個子問題,每個子問題又繼續(xù)遞歸調(diào)用自己，直到"begin<end"這一條件不滿足時，即"begin==end"時，此時只有一個元素，顯然是有序的，這樣再進行下一步合并。

合并：合并的子問題的結(jié)果有個隱含問題，即各個子問題已經(jīng)是排好序的了（從兩個氮元素序列開始合并）。做法是比較兩個子序列的第一個元素小的寫入最終結(jié)果，再往下比較，如下圖所示：

        圖中：待排序數(shù)組為2 4 6  1 3 5

        把2 4 6和 1 3 5 分別存到一個數(shù)組中，比較兩個數(shù)組的第一個元素大小小者存于大數(shù)組中，直到兩小數(shù)組中元素都為32767.

        這里32767 味無窮大，因為 c語言中  int類型是32位，表示范圍是-32768-----32768。用無窮大作為靶子可以減少對兩個小數(shù)組是否為空的判斷，有了靶子，直接判斷大數(shù)組元素個數(shù)次就排完了。 

     在整個過程中執(zhí)行過程示如下圖：

        [[64395]]

      分解+執(zhí)行時自上向下，合并時自下向上。

 代碼奉上：

#include <stdio.h> 
void MERGE(int *A, int b, int m, int e) 
{        
        int l = m-b+1, r = e-m, i; 
        int L[l+1], R[r+1]; 
        for(i=0; i< l; i++) 
        { 
            L[i] = A[b+i]; 
        } 
        for (i=0; i< r; i++) 
        { 
            R[i] = A[m+i+1]; 
        } 
        L[l] = 32767; 
        R[r] = 32767; 
        l = 0; 
        r = 0; 
        for(i=0; i< e-b+1; i++) 
        { 
            if(L[l] < R[r]) 
            { 
                A[b+i] = L[l]; 
                l ++; 
            } 
            else            { 
                A[b+i] = R[r]; 
                r ++; 
            } 
        } 
} 
void MERGE_SORT(int *A, int b, int e) 
{ 
        if(b < e) 
        { 
            int m = (b + e) / 2; 
            MERGE_SORT(A, b, m); 
            MERGE_SORT(A, m+1, e); 
            MERGE(A, b, m, e); 
        } 
} 
int main() 
{ 
        int A[500]; 
        int lens, i; 
        printf("Please Enter the lenghth of array:"); 
        scanf("%d", &lens); 
        printf("Please Enter the elements of the array:"); 
        for(i=0; i< lens; i++) 
            scanf("%d", &A[i]); 
        MERGE_SORT(A, 0, lens-1); 
       printf("the result of the sort is:\n"); 
        for(i=0; i< lens; i++) 
        { 
            printf("%d ", A[i]); 
        } 
        return 0; 
} 

原文鏈接：http://www.cnblogs.com/kaituorensheng/archive/2013/02/21/2919934.html

【編輯推薦】