有声,性爱有声小说在线收听,我欲封天耳根小说

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

C語言實現(xiàn)合并排序

其基本模式如下：

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

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

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

合并：合并子問題的結(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

合并：合并的子問題的結(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    
  
  
  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

網(wǎng)站名稱：C語言實現(xiàn)合并排序
分享鏈接：http://fisionsoft.com.cn/article/dpjjdje.html

新聞中心

其他資訊