归并排序的递归和非递归方法总结 - c++编程基础

归并排序的主要思想是，初始：假设两个子数组都有序，那么就可以通过比较用另外一个数组来存储比较后的有序数组。扩散：于是我们可以把一个数组看成是n个长度为1的有序子数组，通过合并成n/2上界个长度为2的子数组，然后再把n/2个子数组，两两合并成n/4个长度为4的有序子数组.....最后合并成一个有序的长度为n的数组，

递归方法：左边进行递归的有序子序列合并，右边进行有序子序列合并，然后对当前的已经完成有序合并的左右两部分进行合并。

(记住:在递归中后调用的先返回，先调用的后返回)

非递归方法:用len标注进行合并的子数组的长度，初始长度为1，然后两两合并，最后可能会剩下不足2*len的子数组，当不足len的，直接复制过去，>len得，再进行一次到数组末尾的合并。

// SortAlri.cpp : 定义控制台应用程序的入口点。  
//  
  
#include "stdafx.h"  
/*  
对两方都有序的数组进行合并，  
  
*/  
template void Merge(type * a,type * b,int left,int  mid,int right){  
    int i=left,j=mid+1;  
    int k=left;  
    while(i<=mid&&j<=right){  
        if(a[i]<=a[j]){  
          b[k]=a[i];  
          i++;k++;  
        }else {  
        b[k]=a[j];  
        j++;k++;  
        }  
    }  
    if(i<=mid){  
       for( ;i<=mid;i++,k++)  
        b[k]=a[i];  
    }else{  
      
        for(;j<=right;j++,k++)  
            b[k]=a[j];  
    }  
  
}  
  
template void None_MergeSort(type * a,type *b,int lenth){  
    //进行合并的长度，刚开始为1进行两两合并，然后进行长度为2两两合并，直到剩下只有两个有序数组进行合并  
    int len=1;  
    while(len




 void  WholeMerge(type * sourceTable,type * mergedTable,int lenth,int len){//lenth:整个数组的长度-1(，len:进行合并的子数组长度  
    int i=0;  
    while(i<=lenth-2*len){  
        Merge(sourceTable,mergedTable,i,i+len-1,i+2*len-1);  
        i+=2*len;  
    }  
    if(i+len void MergeSort(type * a,type * b,int left,int right){  
      
    if(left(a,b,11);  
    //MergeSort(a,b,0,10);  
    for(int i=0;i<=10;i++)  
        cout<