合并排序

复杂度

java源码

C++源码

C源码

合并排序

合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。

复杂度

时间O(nlogn)

空间O(n)

与快速排序类似

java源码

// 归并分类法

/*

* 采用分治策略，把要分类的序列x1,x2,...,xn一分为二。对它们分别加以分类，然后加以归并为统一的经过排序的序列；

* 适用与对两组或多组有序序列的归并

*/

public static int[] mergeSort(int[] data1,int[] data2)

{

int[] temp=new int[data1.length+data2.length];

int i=0,j=0,iter=0;

for(;i<data1.length&&j<data2.length;)

{

if(data1[i]<=data2[j])

{

temp[iter]=data1[i];

iter++;

i++;

}

else

{

temp[iter]=data2[j];

iter++;

j++;

}

}

for(;i<data1.length;i++,iter++)

{

temp[iter]=data1[i];

}

for(;j<data2.length;j++,iter++)

{

temp[iter]=data2[j];

}

return temp;

}

C++源码

#include<iostream.h>

template<class T>void MergeSort(T a[],int left,int right);

template<class T>void Merge(T c[],T d[],int l,int m,int r);

template<class T>void Copy(T a[],T b[],int l,int r);

void main()

{

int const n(5);

int a[n];

cout<<"Input "<< n <<" numbers please:";

for(int i=0;i<n;i++)

cin>>a[i];

//for(int j=0;j<n;j++)

//b[j]=a[j];

MergeSort(a,0,n-1);

cout<<"The sorted array is"<<endl;

for(i=0;i<n;i++)

cout<<a[i];

cout<<endl;

}

template<class T>

void MergeSort(T a[],int left,int right)

{

if(left < right)

{

int i = (right + left)/2;

T *b=new T[];

MergeSort(a, left, i);

MergeSort(a, i+1, right);

Merge(a, b, left, i, right);

Copy(a,b,left,right);

}

}

template<class T>

void Merge(T c[],T d[], int l, int m, int r)

{

int i = l, j = m+1, k = l;

while(i <= m && j <= r)

{

if(c[i] <= c[j])d[k++]=c[i++];

else d[k++]=c[j++];

}

if(i > m)

{

for(int q = j; q <= r; q ++)

d[k++] = c[q];

}

else

for(int q = i; q <= m; q ++)

d[k++] = c[q];

}

template<class T>

void Copy(T a[],T b[],int l,int r)

{

for(int i=l;i<=r;i++)

a[i]=b[i];

}

C 源码

int mergecpy(int a[],int left,int middle,int right)

{

int b[100];

int i,j,k,n;

i=left;

j=middle+1;

k=middle;

n=0;

//两个序列比较，将有序序列存放在缓冲区b

while(i<=k&&j<=right)

{

if(a[i]>a[j])

{

b[n++] = a[j++];

}

else if(a[i]<a[j])

{

b[n++] = a[i++];

}

else

{

b[n++] = a[j++];

b[n++] = a[i++];

}

}

while(i<=k)

{

b[n++] = a[i++];

}

while(j<=right)

{

b[n++] = a[j++];

}

//将放在临时区的序列拷贝回来

n=0;

for(i=left;i<=right;i++)

{

a[i] = b[n++];

}

}

int mergesort(int a[],int left ,int right)

{

//保证至少有两个数

if(left<right)

{

//一分为二

int middle=(left+right)/2;

//对左合并

mergesort(a,left,middle);

//对右合并

mergesort(a,middle+1,right);

//合而为一

mergecpy(a,left,middle,right);

}

}

C源码

实现原理：首先将序列的每个元素看成是长度为1的有序子序列。然后将这些有序自序列两两合并成长度是2的有序子序列，然后再两两合并...直至合并成长度是n的有序序列。------------------------------------c语言实现---------------------------------------

#include<stdio.h>

void MergeSort(int r[],int n){

int low,high,len;

len=1;//先将序列每元素看成是长度为1的子序列

//只要子序列长度小于n

while(len<n){

low=0;

//从low开始计算，至少存在2个子序列没有合并时继续合并

while(len+low<n){

high=low+len*2-1;

if(high>=n)

high=n-1;

if(!SegmentMerge(r,low,high,len))

return;

low=high+1;

}

len*=2;

}

}

int SegmentMerge(int r[],int low,int high,int len){

int *r1,*r2;

int size1,size2;

int i,j,k;

size1=len;

size2=high-low+1-len;

r1=(int *)malloc(size1*sizeof(int));

r2=(int *)malloc(size2*sizeof(int));

if(r1==NULL||r2==NULL)

return 0;

//将r[low...low+size1-1]与r[low+size1...low+size1+size2-1]复制到r1、r2

for(i=0;i<size1;i++){

r1[i]=r[low+i];

}

for(i=0;i<size2;i++){

r2[i]=r[low+size1+i];

}

i=0;

j=0;

k=low;

while(i<size1&&j<size2){//合并r[low...high]

if(r1[i]<=r2[j])

r[k++]=r1[i++];

else

r[k++]=r2[j++];

}

while(i<size1)

r[k++]=r1[i++];

while(j<size2)

r[k++]=r2[j++];

free(r1);

free(r2);

return 1;

}

void main(){

int r[5]={5,4,3,2,1};

int i;

printf("Before merging sort:");

for(i=0;i<5;i++)

printf("%-3d",r[i]);

printf("\");

MergeSort(r,5);

printf("After merging sort:");

for(i=0;i<5;i++)

printf("%-3d",r[i]);

printf("\");

}

------------------------------------c语言实现---------------------------------------