mergesort.java

来自「最近点对问题的图形界面实现」· Java 代码 · 共 57 行

package firstproblem;
/**
 * MergeSort用于归并排序
 * @author 何腾飞
 *
 */
public class MergeSort {
	public static void mergeSort(Comparable []a){
		Comparable []b = new Comparable[a.length];
		int s = 1;
		while(s<a.length){
			mergePass(a,b,s);
			s+=s;
			mergePass(b,a,s);
			s+=s;
		}
	}
	public static void mergePass(Comparable []x,Comparable []y,int s){
		int i =0 ;
		while(i<=x.length-2*s){
			merge(x,y,i,i+s-1,i+2*s-1);
			i = i+2*s;
		}
		if(i+s<x.length){
			merge(x,y,i,i+s-1,x.length-1);
		}
		else{
			for(int j=i;j<x.length;j++){
				y[j] = x[j];
			}
		}
	}
	public static void merge(Comparable []c,Comparable[]d,int l,int m,int r){
		int i = l;
		int j = m+1;
		int k = l;
		while((i<=m)&&(j<=r)){
			if(c[i].compareTo(c[j])<=0){
				d[k++] = c[i++];
			}
			else{
				d[k++] = c[j++];
			}
			if(i>m){
				for(int q=j;q<=r;q++){
					d[k++] = c[q];
				}
			}
			else if(j>r){
				for(int q=i;q<=m;q++){
					d[k++] = c[q];
				}
			}
		}
	}
}