精易论坛

标题: C语言实现合并排序 [打印本页]

---

作者: ljmst    时间: 2013-3-2 23:20
标题: C语言实现合并排序

递归算法是把一个问题分解成和自身相似的子问题，然后再调用自身把相应的子问题解决掉。这些算法用到了分治思想。

其基本模式如下：
分解：把一个问题分解成与原问题相似的子问题
解决：递归的解各个子问题
合并：合并子问题的结果得到了原问题的解。
现在就用递归算法，采用上面的分治思想来解合并排序。
合并排序（非降序）
分解：把合并排序分解成与两个子问题
伪代码：

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)
  

解决：递归的解各个子问题,每个子问题又继续递归调用自己，直到"begin<end"这一条件不满足时，即"begin==end"时，此时只有一个元素，显然是有序的，这样再进行下一步合并。
合并：合并的子问题的结果有个隐含问题，即各个子问题已经是排好序的了（从两个氮元素序列开始合并）。做法是比较两个子序列的第一个元素小的写入最终结果，再往下比较，如下图所示：

图中：待排序数组为2 4 6  1 3 5
把2 4 6和 1 3 5 分别存到一个数组中，比较两个数组的第一个元素大小小者存于大数组中，直到两小数组中元素都为32767.
这里32767 味无穷大，因为 c语言中  int类型是32位，表示范围是-32768-----32768。用无穷大作为靶子可以减少对两个小数组是否为空的判断，有了靶子，直接判断大数组元素个数次就排完了。
在整个过程中执行过程示如下图：

分解+执行时自上向下，合并时自下向上。
代码奉上：

#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 = A[b+i];
          }
•         for (i=0; i< r; i++)
          {
•             R = 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);
•         MERGE_SORT(A, 0, lens-1);
         printf("the result of the sort is:\n");
•         for(i=0; i< lens; i++)
          {
•             printf("%d ", A);
          }
•         return 0;
• }
  

---

作者: 素顏じ亦傾城ジ    时间: 2013-3-2 23:23
路过 .......................

---

作者: Cand    时间: 2013-3-3 12:06
牛逼呢、.....

---

欢迎光临 精易论坛 (https://125.confly.eu.org/)

Powered by Discuz! X3.4