什么是合并排序介绍

合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。

合并排序基本概念

复杂度

最坏时间复杂度

最好时间复杂度

空间复杂度

与快速排序类似

合并排序实现

合并排序JAVA

public static void mergeSort(intarray){    int length=array.length;  int middle=length/2;  if(length>1){    intleft=Arrays.copyOfRange(array,0,middle);//拷贝数组array的左半部分    intright=Arrays.copyOfRange(array,middle,length);//拷贝数组array的右半部分    mergeSort(left);//递归array的左半部分    mergeSort(right);//递归array的右半部分    merge(array,left,right);//数组左半部分、右半部分合并到Array  }}//合并数组，升序private static void merge(intresult,intleft,intright){  int i=0,l=0,r=0;  while(l<left.length&&r<right.length){    if(left<right){      result=left;      i++;      l++;    }else{      result=right;      i++;      r++;   }  }  while(r<right.length){//如果右边剩下合并右边的    result=right;    r++;    i++;  }  while(l<left.length){    result=left;    l++;    i++;  }}

合并排序C、C++语言

程序1

#include #include void mergesort(int*a,int length){    int step;    int*p,*q,*t;    int i,j,k,len1,len2;    int *temp;        step=1;    p=a;    q=(int*)malloc(sizeof(int)*length);    temp=q;    while(step<length){        i=0;        j=i+step;        k=i;        len1=i+step<length?i+step:length;        len2=j+step<length?j+step:length;        while(i<length){            while(i<len1&&j<len2){                q=p<p?p:p;            }            while(i<len1){                q=p;            }            while(j<len2){                q=p;            }            i=j;            j=i+step;            k=i;            len1=i+step<length?i+step:length;            len2=j+step<length?j+step:length;        }        step*=2;        t=p;        p=q;        q=t;    }    if(a!=p){        memcpy(a,p,sizeof(int)*length);    }        free(temp);}void main(void){int arrary={9,6,1,3,8,4,2,0,5,7};mergesort(arrary,10);}

程序2

排序位于,*r=new T;//要合并的两个数组    memcpy(l,arry + start,sizeof(T)*lsize);    memcpy(r,arry + p,sizeof(T)*rsize);//将要合并的数组复制    int lnow=0,rnow=0,i;//未合并的数字的位置    for(i=0;lnow<lsize&&rnowr)//取较大的数        {            arry=l;            lnow++;        }        else        {            arry=r;            rnow++;        }    }    if(lnow==lsize&&rnow!=rsize)//其中一个数组合并完以后，复制剩下的数据    {        memcpy(arry+start+i,r+rnow,sizeof(T)*(rsize-rnow));    }    else if(rnow==rsize&&lnow!=lsize)    {        memcpy(arry+start+i,l+lnow,sizeof(T)*(lsize-lnow));    }    delete l;    delete r;//清理内存    //return ;}//排序函数time:O(nlgn)templatevoid MergeSort(T *arry,int start,int end){    if(end-start > 1)//当元素个数为1时直接返回    {        int p=(start + end)/2;//切割数组        MergeSort(arry,start,p);        MergeSort(arry,p,end);//分别排序        Merge(arry,start,p,end);//合并数组    }}int main(){         int arr={7,3,4,7,10,9,1,5,3,7};        MergeSort(arr,0,10);    for(int i=0;i<10;i++)    {        cout<<arr<<\" \"<<endl;    }    return 0;}