Java归并排序

今天我来讲讲归并排序的原理：归并排序采用了分治的原理，首先将一个数组进行拆分至不能拆为止，然后将各个最小的最小数组进行排序，按原路进行排序到临时数组里，最后将临时数组的元素放回到原数组。

代码如下:

import java.util.Arrays;

public class Main{
	public static void main(String[] args) {
		int[] arr= {10,50,42,86,88,78};
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}
	public static void sort(int[] arr) {
		if(arr==null||arr.length==0) {
			System.out.println("你输入的数组有误");
			return;
		}
		int len=arr.length;
		//归并方法主体
		mergeSort(arr,0,len-1);
	}
	public static void mergeSort(int[] arr,int start,int end) {
		//终止条件
		if(start>=end) {
			return;
		}
		int m=(start+end)/2;
        //递归自己调用自己，进行拆分数组
		mergeSort(arr,start,m);
		mergeSort(arr,m+1,end);

		merge(arr,start,m,end);
	}
	public static void merge(int[] arr,int start,int m,int end) {
        //这个方法主要是进行排序和放回到原数组
		int[] temp=new int[arr.length];
		//前半段数据游标
		int i=start;
		//后半段数据游标
		int j=m+1;
		//临时数组游标
		int k=start;
		while(i<=m&&j<=end) {
			if(arr[i]>arr[j]) {
				temp[k++]=arr[i++];
			}else {
				temp[k++]=arr[j++];
			}
		}
		//最后将剩余的数据全部追加到临时数组
		while(i<=m) {
			temp[k++]=arr[i++];
		}
		while(j<=end) {
			temp[k++]=arr[j++];
		}
		//将临时数组的数据全部还给原数组
		for(int y=start;y<=end;y++) {
			temp[y]=arr[y];
		}
	}
}

大概就是这些了。