java 归并排序

分而治之，归并排序

算法简单易懂，第一次编写错误，误把原数组下表当做临时数组考虑，结果可想而知，访问越界

下面是正确代码

import java.util.Scanner;

public class MergeSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int  n=Integer.parseInt(scanner.next());;
		int []a=new int[n];
		for (int i = 0; i < n; i++)
		{
			a[i]=Integer.parseInt(scanner.next());
		}
		mergeSort(a,0,n-1);
		for (int i = 0; i < n; i++) {
			System.out.print(a[i]+"  ");
		}
	}

	public static void mergeSort(int a[], int begin, int end) 
	{
		if ((end-begin)>=1) {
			mergeSort(a, begin, begin+(end-begin)/2);
			mergeSort(a, begin+(end-begin)/2+1, end);
			merge(a, begin, begin+(end-begin)/2, end);
		}
	}
	
	public static void merge(int a[], int b, int m, int e)
	{
		int []arry1=new int[m-b+1]; //temporary array
		int []arry2=new int[e-m];
		int i=b;
		int j=m+1;
		int k=0;
		for ( k = 0; k < arry1.length;) 
		{
			arry1[k++]=a[i++];
		}
		for ( k = 0; k < arry2.length;) 
		{
			arry2[k++]=a[j++];
		}
		i=0;
		j=0;
		for ( k = b; i<arry1.length&&j<arry2.length; k++)
		{
			if(arry1[i]<arry2[j])	
			{
				a[k]=arry1[i++];
			}
			else
			{
				a[k]=arry2[j++];
			}
		}
		for ( ; i<arry1.length; k++) 
		{
				a[k]=arry1[i++];
		}
		for ( ; j<arry2.length; k++)
		{
			a[k]=arry2[j++];
		}
	}
}

java 归并排序,布布扣,bubuko.com

java 归并排序

原文：http://blog.csdn.net/biruixing/article/details/38663473