合併排序

合併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的套用。

合併排序法是將兩個（或兩個以上）有序表合併成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合併為整體有序序列。

將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。合併排序也叫歸併排序。

基本介紹

• 中文名：合併排序
• 特點：建立在歸併操作上
• 屬性：有效的排序算法
• 方法：分治法

基本概念

複雜度

最壞時間複雜度

最好時間複雜度

空間複雜度

與快速排序類似

實現

JAVA

public static void mergeSort(int[]array){    int length=array.length;  int middle=length/2;  if(length>1){    int[]left=Arrays.copyOfRange(array,0,middle);//拷貝數組array的左半部分    int[]right=Arrays.copyOfRange(array,middle,length);//拷貝數組array的右半部分    mergeSort(left);//遞歸array的左半部分    mergeSort(right);//遞歸array的右半部分    merge(array,left,right);//數組左半部分、右半部分合併到Array  }}//合併數組，升序private static void merge(int[]result,int[]left,int[]right){  int i=0,l=0,r=0;  while(l<left.length&&r<right.length){    if(left[l]<right[r]){      result[i]=left[l];      i++;      l++;    }else{      result[i]=right[r];      i++;      r++;   }  }  while(r<right.length){//如果右邊剩下合併右邊的    result[i]=right[r];    r++;    i++;  }  while(l<left.length){    result[i]=left[l];    l++;    i++;  }}

C/C++語言

程式1

/****************************//*author:不辭遠*//****************************/#include <malloc.h>#include <stdlib.h>void mergesort(int*a,intlength){    int step;    int*p,*q,*t;    inti,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[k++]=p[i]<p[j]?p[i++]:p[j++];            }            while(i<len1){                q[k++]=p[i++];            }            while(j<len2){                q[k++]=p[j++];            }            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

排序位於[begin, end)中的整數

void sort(int*begin,int*end){int size=end-begin;int*p,*p1,*p2,*mid=begin+size/2;if(size<=1)return;//邊界條件sort(begin,mid);//遞歸求解sort(mid,end);p=(int*)malloc(size*sizeof(int));//申請臨時空間for(p1=begin,p2=mid;p1!=mid||p2!=end;)//合併有序表*p++=(p2==end||p1!=mid&&*p1<*p2)?(*p1++):(*p2++);for(p-=size;begin!=end;)//回填*begin++=*p++;free(p-size);//釋放臨時空間}

程式3

//C++#include<string>#include<iostream>using namespace std;//合併排序//合併兩部分有序數組time:O(n)template<typename T>void Merge(T  *arry,int start,int p,int end){    int lsize=p-start,rsize=end-p;//兩個數組的大小    T * l=new T[lsize],*r=new T[rsize];//要合併的兩個數組    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&&rnow<rsize;i++)    {        if(l[lnow]>r[rnow])//取較大的數        {            arry[start+i]=l[lnow];            lnow++;        }        else        {            arry[start+i]=r[rnow];            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)template<typename T>void 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[10]={7,3,4,7,10,9,1,5,3,7};        MergeSort(arr,0,10);    for(int i=0;i<10;i++)    {        cout<<arr[i]<<" "<<endl;    }    return 0;}