日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
C語言實(shí)現(xiàn)合并排序

其基本模式如下：

成都創(chuàng)新互聯(lián)公司專注于封丘網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供封丘營銷型網(wǎng)站建設(shè)，封丘網(wǎng)站制作、封丘網(wǎng)頁設(shè)計(jì)、封丘網(wǎng)站官網(wǎng)定制、小程序開發(fā)服務(wù)，打造封丘網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供封丘網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。

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

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

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

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

合并排序（非降序）

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

偽代碼：

 
 
 
 
    
  
  
  
  
  1. MERGE_SORT(A, begin, end) 
    2.   
  
  
  
  2. if begin < end 
    3.   
  
  
  
  3.    then mid<- int((begin + end)/2) 
    4.   
  
  
  
  4.            MERGE_SORT(A, begin, mid) 
    5.   
  
  
  
  5.            MERGE_SORT(A, mid+1, end) 
    6.   
  
  
  
  6.            MERGE(A, begin, mid, end) 
    7.

解決：遞歸的解各個子問題,每個子問題又繼續(xù)遞歸調(diào)用自己，直到"begin

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

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

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

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

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

        [[64395]]

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

 代碼奉上：

 
 
 
 
    
  
  
  
  
  1. #include  
    2.   
  
  
  
  2. void MERGE(int *A, int b, int m, int e) 
    3.   
  
  
  
  3. {        
    4.   
  
  
  
  4.         int l = m-b+1, r = e-m, i; 
    5.   
  
  
  
  5.         int L[l+1], R[r+1]; 
    6.   
  
  
  
  6.         for(i=0; i< l; i++) 
    7.   
  
  
  
  7.         { 
    8.   
  
  
  
  8.             L[i] = A[b+i]; 
    9.   
  
  
  
  9.         } 
    10.   
  
  
  
  10.         for (i=0; i< r; i++) 
    11.   
  
  
  
  11.         { 
    12.   
  
  
  
  12.             R[i] = A[m+i+1]; 
    13.   
  
  
  
  13.         } 
    14.   
  
  
  
  14.         L[l] = 32767; 
    15.   
  
  
  
  15.         R[r] = 32767; 
    16.   
  
  
  
  16.         l = 0; 
    17.   
  
  
  
  17.         r = 0; 
    18.   
  
  
  
  18.         for(i=0; i< e-b+1; i++) 
    19.   
  
  
  
  19.         { 
    20.   
  
  
  
  20.             if(L[l] < R[r]) 
    21.   
  
  
  
  21.             { 
    22.   
  
  
  
  22.                 A[b+i] = L[l]; 
    23.   
  
  
  
  23.                 l ++; 
    24.   
  
  
  
  24.             } 
    25.   
  
  
  
  25.             else            { 
    26.   
  
  
  
  26.                 A[b+i] = R[r]; 
    27.   
  
  
  
  27.                 r ++; 
    28.   
  
  
  
  28.             } 
    29.   
  
  
  
  29.         } 
    30.   
  
  
  
  30. } 
    31.   
  
  
  
  31. void MERGE_SORT(int *A, int b, int e) 
    32.   
  
  
  
  32. { 
    33.   
  
  
  
  33.         if(b < e) 
    34.   
  
  
  
  34.         { 
    35.   
  
  
  
  35.             int m = (b + e) / 2; 
    36.   
  
  
  
  36.             MERGE_SORT(A, b, m); 
    37.   
  
  
  
  37.             MERGE_SORT(A, m+1, e); 
    38.   
  
  
  
  38.             MERGE(A, b, m, e); 
    39.   
  
  
  
  39.         } 
    40.   
  
  
  
  40. } 
    41.   
  
  
  
  41. int main() 
    42.   
  
  
  
  42. { 
    43.   
  
  
  
  43.         int A[500]; 
    44.   
  
  
  
  44.         int lens, i; 
    45.   
  
  
  
  45.         printf("Please Enter the lenghth of array:"); 
    46.   
  
  
  
  46.         scanf("%d", &lens); 
    47.   
  
  
  
  47.         printf("Please Enter the elements of the array:"); 
    48.   
  
  
  
  48.         for(i=0; i< lens; i++) 
    49.   
  
  
  
  49.             scanf("%d", &A[i]); 
    50.   
  
  
  
  50.         MERGE_SORT(A, 0, lens-1); 
    51.   
  
  
  
  51.        printf("the result of the sort is:\n"); 
    52.   
  
  
  
  52.         for(i=0; i< lens; i++) 
    53.   
  
  
  
  53.         { 
    54.   
  
  
  
  54.             printf("%d ", A[i]); 
    55.   
  
  
  
  55.         } 
    56.   
  
  
  
  56.         return 0; 
    57.   
  
  
  
  57. } 
    58.

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


分享標(biāo)題：C語言實(shí)現(xiàn)合并排序
文章分享：http://www.dlmjj.cn/article/dpjjdje.html