一.什么是归并排序

    归并排序就是将多个有序的数据段合成一个有序的数据段，如果参与合并的只有两个有序的数据段，则称为二路归并。与快速排序和堆排序相比，其最大的特点是一种稳定的算法，算法的平均时间复杂度O(nlog2n)。

二.归并排序的基本思路

    (1).对于一个原始的待排序表，可以将R[1]到R[n]可以看做是n个长度为1的有序表，即分解。

    (2).进行第一趟归并，即将上述的n个子序两两合并，得到 n/2向上取整 个有序表，若n为奇数，则归并到最后一个子序列长度为1，即合并。

    (3).再将两个 n/2向上取整 个有序表两两合并，如此重复下去，直到得到一个长度为n的有序表，这种排序方法也叫2-路归并排序。

     原理如下图

 

                                         

                                                      以[63，95，84，46，18，24，27，31，46]为例

三. 实现归并排序之前，需要调用"一次归并“和”一趟归并“，那什么是一次归并？什么是一趟归并呢？

     （1）.一次归并：把首尾相接的两个有序表R[low...mid]、R[mid+1...high]归并成有序表R[low...high].

      (2) .一趟归并：把一些相互连接的有序表依次两两归并成一些更大的有序表。

 

 1.一次归并代码如下

//一次归并排序 void Merge(int low,int m,int high)         {                // 将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]            int i=low;    int j=m+1;    int p=0;            //置初始值          int *R1;            //R1是局部向量        R1=(int *)malloc((high-low+1)*sizeof(int));          if(!R1)                        //申请空间失败           {                puts("空间申请失败");               return;           }           while(i<=m&&j<=high)                  // 两子文件非空时取其小者输出到R1[p]上               R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];           while(i<=m)                          // 若第1个子文件非空，则复制剩余记录到R1中                 R1[p++]=R[i++];           while(j<=high)                      // 若第2个子文件非空，则复制剩余记录到R1中              R1[p++]=R[j++];           for(p=0,i=low;i<=high;p++,i++)                 R[i]=R1[p];                    // 归并完成后将结果复制回R[low..high] }

2.一趟归并排序代码如下

1 //一趟归并排序  2 void mergepass(int n,int len)  3 { 4     int i,t; 5     i=1; 6     while(i<=n-2*len+1) 7     { 8         Merge(i,i+len-1,i+2*len-1); 9         i=i+2*len;10     }11     if(i+len-1

 

   写完”一次归并“和"一趟归并”后，接下来就是编写二路归并了，二路归并就是调用“一次归并”和“一趟归并”，最后组合成一个长度为n的有序表。

二路归并有递归的方法和非递归的方法（即迭代方法），下面就来看一下递归与非递归的实现

(1)非递归的方法

1 void mergesort(int n)       //非递归的二路归并实现 2 { 3     int len; 4     int *R1;            // R1是局部向量 5     len=1; 6     while(len

(2)递归方法实现

1 //递归的二路归并排序  2 void MergeSortDC(int low,int high)  3 {                                     //用分治法对R[low..high]进行二路归并排序         4    int mid;         5    if(low

     讲到这里，归并排序的思想方法就讲完了，然后就可以自己写main()函数了，然后调用上面的自定义函数就可以实现了

下面是完整的代码实现，仅供参考,如有问题，欢迎指教

1 #include 
     
          2 #include
      
         3 #include
       
          4 #define MAX 100   5 int R[MAX];     6 //一次归并排序   7 void Merge(int low,int m,int high)           8 {                // 将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]          9     int i=low; 10     int j=m+1; 11     int p=0;            //置初始值       12     int *R1;            //R1是局部向量     13     R1=(int *)malloc((high-low+1)*sizeof(int));       14     if(!R1)                        //申请空间失败        15     {          16        puts("空间申请失败");         17        return;        18     }        19     while(i<=m&&j<=high)                  // 两子文件非空时取其小者输出到R1[p]上        20         R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];        21     while(i<=m)                          // 若第1个子文件非空，则复制剩余记录到R1中          22         R1[p++]=R[i++];        23     while(j<=high)                      // 若第2个子文件非空，则复制剩余记录到R1中       24         R1[p++]=R[j++];        25     for(p=0,i=low;i<=high;p++,i++)          26         R[i]=R1[p];                    // 归并完成后将结果复制回R[low..high]  27 }    28 //递归的二路归并排序  29 void MergeSortDC(int low,int high)  30 {                                     //用分治法对R[low..high]进行二路归并排序         31    int mid;         32    if(low
        
         MAX)   70     {    71         printf("n 必须大于 0 小于 %d.\n",MAX);    72         exit(0);   73     }    74     puts("请依次输入数组的数据:");   75     for(i=1;i<=n;i++)    76       scanf("%d",&R[i]);    77     puts("排序前的数组数据为:");   78     for(i=1;i<=n;i++)    79        printf("%4d",R[i]);   80    printf("\n\n      递归与非递归的合并排序       \n"); 81    printf("\n      1.递归合并排序               \n"); 82    printf("\n      2.非递归合并排序             \n"); 83    printf("\n请输入您的选择："); 84    scanf("%d",&d); 85    if(d==1) 86    { 87     MergeSortDC(1,n);    88     puts("\n递归归并排序后:");   89     for(i=1;i<=n;i++)    90        printf("%4d",R[i]);   91    }  92    else if(d==2)  93    { 94        mergesort(n); 95        puts("\n非递归归并排序后:");   96     for(i=1;i<=n;i++)    97        printf("%4d",R[i]);  98    } 99    else100      printf("您输入的菜单号有误！"); 101 }