mergesort.java

合并排序算法在java语言下的实现

public class mergeSort
{

 public static void main(String args[]){

 int a[]={3,6,4,12,8,5,14};

 mergeSort(a);

 aprint(a);
 
} 

public static void mergeSort(int a[]){

int b[]=new int[a.length];
int s=1;
while(s<a.length){
 mergePass(a,b,s);//合并到数组b
s+=s;
mergePass(b,a,s);//合并到数组a
s+=s;
}
}

public static void mergePass(int x[],int y[] ,int s){

//合并大小为s的相邻数组

int i=0;
while(i<=(x.length-2*s)){
//合并大小为s的相邻二段子数组
merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;
}
//剩下的元素个数小于2s
if((i+s)<x.length) merge(x,y,i,i+s-1,x.length-1);
else
//复制到y
for(int j=i;j<x.length;j++)
 y[j]=x[j];
}


public static void merge(int c[],int d[],int l,int m,int r){

//合并c[l:m]和c[m+1:r]到d[l: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];

}

public static void aprint(int b[]){
 
 System.out.println("数组长度:"+b.length);
System.out.println("合并排序后输出如下:");
for(int i=0;i<b.length;i++)
System.out.println(b[i]);
}
}