归并排序的非递归算法完成 A8站源码交易平台

归并排序在各种数据结构的教材上多给出的是递归算法，对非递归算法要么没给出，要么语焉不详，看了让人云里雾里．

从归并排序递归算法原理上看，　对排序数组不断递归两分，当递归到最底层时，实质上是把数据分红两个或单个的组，对两个一组的数据又分红左右两半，然后兼并排序，这样但凡两个一组的元素都成排序状况．至于单个数据的无需排序．　然后再每两组一个单元，再作兼并排序，这样不断地每两个单元兼并，一向到最终兼并一个排序数组．A8站源码交易平台

 

因而，非递归算法，　能够直接从最底层的兼并开端，先把数据两两成组，对各个组排序，再四四成组，又对各组排序．．再八八成组，这样不断进行下去，一向到兼并成一个数组停止．

代码入下:

 

#include 
 using namespace std;
 void MergeSort(int array[], int left, int right);
 void MergeSort2(int array[],int len)   ; //非递归算法 
 void Merge(int a[], int p, int q, int r) ;
 int main()
 {
     int i=0; 
    int a[] = {15,4,9,12,7,6,5,1,23,2,73,34,45,22,55,44,26,71,89,91,33,82}; //有10个元素 
   // MergeSort(a,0,10-1);
    MergeSort2(a,22);
    for(int i=0;i<22;i++)
        cout<< a[i] <<" ";
    cout <<endl;
 
 }
 /*
     array 待排序子序列  left 子序列最左面元素下标,right  子序列最右边元素下标    
 */
 void MergeSort(int array[], int left, int right) //递归算法 
 {
        if(left<right){
 //     left表明从子序列的哪个索引开端，mid表明子序列中心的方位
            int mid = (left+right)/2; 
//    分红左右两半持续递归调用  调用    
            MergeSort(array,left,mid);       
            MergeSort(array,mid+1,right);
//前面两次递归调用后, 左右两东床序列都是有序数列了,再调用Merge 进行兼并 
            Merge(array,left,mid,right);
        }
}
/*
    array 数组名,  len 数组长度 
*/
void MergeSort2(int array[],int len)   //非递归算法 
{
    int  left,mid,right; //调用兼并函数Merge的左中右三个参数 
    
    int  k=1,j;   
    while(k<len-1)
     {
        k=k*2;     //k是子序列的巨细 ,从2开端, 即每两个元素构成一个子序列, 下一次循环每4个元素构成一个子序列...
        for(j=0;k*j<len;j++)
         {
            left  =  k*j;
            mid   =  left+(k/2)-1;
            
            right = left+k-1;
            if(right>len-1)
                right=len-1;
                
//          子序列区分后，最终一个序列是奇数序列不成对 即right<=mid, 不必归并        
            if(right>mid) {
                Merge(array,left, mid  ,right);    
            }
                
        }
            
    }
}
    
void Merge(int array[], int left, int mid, int right) 
{
//        n1和n2别离表明左面序列和右边序列的长度。左面从left开端包含mid，右边从mid+1开端
        int n1 = mid-left+1;
        int n2 = right-mid;
        int *L = new int[n1];
        int *R = new int[n2];
//        k用来表明当时遍历的数组a的索引
        int i=0,j=0,k=0;
//        别离给L和R赋值
        for(i=0,k=left; i<n1; i++,k++){             L[i] = array[k];
        }
//        从右边开端
        for(j=0,k=mid+1; j<n2; j++,k++){             R[j] = array[k];
        }
//        比较巨细,从小到大摆放
        for(i=0,j=0,k=left; i<n1&&j<n2; k++){             if(L[i] > R[j]){
                array[k] = R[j];
                j++;
            }else{
                array[k] = L[i];
                i++;
            }
        }
//        通过前面的兼并后, 将两个数组中剩余的数放到array中, 其实只要一个数组有剩余未兼并的数据 
        if(i<n1){
             for(j=i; j<n1; j++,k++){                 array[k] = L[j];
            }
        }
        if(j<n2){
             for(i=j; i<n2; i++,k++){                 array[k] = R[i];
            }
        }
    }



A8站源码交易平台