归并算法

假设我们现在有一组数组Array。

现在我们把他分成两部分。

和

我们分别对2,1,4,8排序，和对5，7，3，6排序。

在2,1,4,8中我们有分别把它分为两部分。5,7,3,6同理。

2,1,4,8变成2,1和4,8。5,73,6变成5，7和3，6.

然后将分出来的数比较大小，创建一个数组，把比较好的数保存起来。再赋给原数组。

接下看代码实现。

package paixu;

public class C {
	
	public static void Procce(int arr[] ,int L ,int R ){
		if(R == L){
			return ;
		}
		int mid = (L + R) / 2  ;
		Procce(arr, L, mid); //左边分支
		Procce(arr, mid+1, R); //右边分支
		merge(arr,L,R,mid); //比较大小
	}
	

	private static void merge(int[] arr, int L, int R,int mid) {
		int [] help = new int[R-L+1] ;  //定义一个数组又来装比较之后数
		int   i = 0 ;
		int p0 = L ,p1 = mid + 1 ;
		//比较
		while(p0 <= mid && p1 <= R){
			help[i++] = arr[p0]<arr[p1] ? arr[p0++]:arr[p1++] ;
		}
		//必有一个出界,将没有出界在保存到辅助数组中。
		while (p0 <= mid) {
			help[i++] = arr[p0++];
		}
		while (p1 <= R) {
			help[i++] = arr[p1++];
		}
		for (int j = 0; j < help.length; j++) {
			arr[j+L] = help[j] ;
		}
	}
	public static void main(String[] args) {
		int [] arr = new int[]{2,1,4,8,5,7,3,6} ;
		Procce(arr, 0, arr.length-1);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+".");
		}
	}
	
}