mergesort.java

mergesort java 实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class COMP7712_WYin_1_4b {
	
	// read int number from the standard input,
	// if the input is not "number", the value "-9999" will be assigned 
	public static int readnumber()
	{
	    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	    String s = null;
	    int r = -9999;
	    try {
	        s = in.readLine();
	    }
	    catch (IOException e) {
	        e.printStackTrace();
	    }
	    try {
	    	r = Integer.parseInt(s);
	        //System.out.println("which is a number");
	    }
	    catch (NumberFormatException e) {
	        System.out.println("which is not a number");
	    }
	    return r;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int m=0,n=0;
	    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	    String s = null;
	    
//1.initialize list A	 	    
		do
		{
	    System.out.println("Please input the size of list A:");
		m = readnumber();
		}while(m<0||m==0);
	    System.out.println("Elements of list A:");
		int[] A = new int[m];	    
	    for(int i=0;i<m;i++)
	    	A[i] = readnumber();
	    System.out.print("list A: ");
	    for(int i=0;i<m;i++)
	    	System.out.print(A[i]+" ");
	    System.out.println();
    
//2.initialize list B
	    do
	    {
		System.out.println("=====\nPlease input the size of list B:");
		n = readnumber();
		}while(n<0||n==0);
		System.out.println("Elements of list B:");
		int[] B = new int[n];	    
	    for(int i=0;i<n;i++)
	    	B[i] = readnumber();
	    System.out.print("list B: ");
	    for(int i=0;i<n;i++)
	    	System.out.print(B[i]+" ");
	    System.out.println();

		int k=0;
		int[] C = new int[m+n];
	    for(k=0;k<m;k++)
	    	C[k] = A[k];
	    for(k=0;k<n;k++)
	    	C[m+k] = B[k];
	    System.out.print("The orginal list C: ");
	    for(k=0;k<m+n;k++)
	    	System.out.print(C[k]+" ");		
	    System.out.println();
	    
	    mergesort(m+n,C);
	    
	    System.out.print("The last list C: ");
	    for(k=0;k<m+n;k++)
	    	System.out.print(C[k]+" ");	 
	}

	
	public static int[] merge(int m,int A[],int n,int B[],int C[])
	{
		int i=0,j=0,k=0,t=0;
		while(i<m && j<n)
		{
			C[k++] = A[i]<B[j]?A[i++]:B[j++];
		}
		if(i==m)
		{
			for(t=j;t<n;t++)
				C[k++] = B[t]; 
		}
		else if(j==n)
		{
			for(t=i;t<m;t++)
				C[k++] = A[t]; 
		}
		return C;
	}

	public static int[] mergesort(int size,int a[])
	{
		int m = size/2;
		int n = size-m;
		int[] A = new int[m];
		int[] B = new int[n];
		for (int i=0;i<m;i++)
			A[i] = a[i];
		for (int i=0;i<n;i++)
			B[i] = a[m+i];
		int[] C = new int[m+n];
		if(size > 1)
		{
			merge(m,mergesort(m,A),n,mergesort(n,B),C);
			for(int i=0;i<size;i++)
				a[i] = C[i];
			return a;
		}
		else
			return a;
		
	}

	
}