mergesort.java

java编写的算法,其中包括三种排序方法呀

import java.util.*;

/*归并排序
 *将数组中的各个数两两合并（两个数），直到合并的长度为（n/2）（这些小的数也是有序的），
 *然后成一个有序的数组；
 **/
public class MergeSort{
	public static void main(String args[]){
		int n=20;
		int k=1; 
		// 获得数据源
		Random rand=new Random();
		int arraynum[]=new int[n];
		int swap[]=new int[n];
		System.out.println("DataSource:");
		for(int i=0;i<n;i++){
			arraynum[i]=Math.abs(rand.nextInt()%100);
			System.out.print(arraynum[i]+"  ");
		}
		System.out.println("");
		
		
		//调用归并排序方法
		while(k<n){
			M_S(arraynum,n,swap,k);
			for(int i=0;i<n;i++){
				arraynum[i]=swap[i];
			}
			k=2*k;
		}
		
		System.out.println("Merge_SortData:");
		for(int i=0;i<n;i++){
			System.out.print(arraynum[i]+"  ");
		}
		System.out.println("");
		
	}
	
	//归并排序方法。
	static void M_S(int a[],int n,int swap[],int k){
		int l1,l2,u1,u2,i,j,m=0;
		l1=0;
	
		//确定两个要合并的小数组的上下界,把他们合并成一个小数组再排序
		while(l1+k<=n-1){
			l2=l1+k;
			u1=l2-1;
			u2=(l2+k-1<n)?l2+k-1:n-1;
			
			//合并后再将这个小数组排序成一个在序列
			for(i=l1,j=l2; i<=u1&&j<=u2; m++){
				
				if(a[i]<=a[j]){
					swap[m]=a[i];
					i++;
				}else{
					swap[m]=a[j];
					j++;
				}
			}
			
			
			//将子数组的其他元素放入swap数组中
			while(i<=u1){
				swap[m]=a[i];
				m++;
				i++;
				
			}
			
			while(j<=u2){
				swap[m]=a[j];
				m++;
				j++;
					
			}
			
			l1=u2+1;
			
		}
		//把没有合并的照列写入数组中.
		for(i=l1;i<n;i++,m++) swap[m]=a[i];
		
	}
}