排序算法（Java随笔）—归并排序

归并排序（Merge Sort）：将多个有序数据表合并为一个有序数据表，如果被合并的数据表只有两个，则叫二路归并。

二路归并排序的原理步骤：

1. 将长度为n的原数据表分割为n个长度为1的子表，两两合并得到n/2个长度为2的有序子表
2. 将长度为2的有序子表两两合并得到n/4个长度为4的有序子表
3. 重复以上步骤，直到最后的子表长度为n，排序完成

原理总结：先通过递归分解序列，再有序的合并序列即完成了归并。

归并排序算法实例——代码实现：

//归并排序(分两步):先递归，再合并(将数组递归分解，再进行排序合并)
	//1、合并数组
	void mergeArray(int[] data,int start,int mid,int end){
		/*
		 * @param data[] 需要被排序的数组
		 * @param start 数组的开始
		 * @param end 数组的结尾
		 */
		int[] temp=new int[end-start+1];//存放排序好的数组,数组大小为当前参与排序的数据个数
		int s=start;//数组左引用
		int e=mid+1;//数组右引用
		int k=0;//数组temp[]的下一个位置的指针，每存放一个数据，k增一
		//左右合并排序
		while(s<=mid&&e<=end){
			if(data[s]<=data[e]){
				temp[k++]=data[s++];
			}else{
				temp[k++]=data[e++];
			}
		}
		//合并数组左边剩余数组
		while(s<=mid){
			temp[k++]=data[s++];
		}
		//合并数组右边剩余数组
		while(e<=end){
			temp[k++]=data[e++];
		}
		//以排序好的部分数据覆盖掉原数组中的数据
		for(int i=0;i<temp.length;i++){
			data[start+i]=temp[i];
		}
	}
	//2、递归分解数组(首先将数组递归为长度为1的序列，然后依次出栈长度为2,4...)
	/*
	 * 将数组递归分解为长度为1后、通过合并数组将相邻两个数据变为有序数列(排序)
	 * 如第一个数据为23、第二个数据为12、合并后第一个数据为12、第二个数据为23
	 * 然后再出栈长度为2的序列、通过合并数组将其变为有序序列...
	 */
	int[] mergeSort(int[] data,int start,int end){
		int mid=(end-start)/2+start;
		if(start<end){
			//左递归
			mergeSort(data,start,mid);
			//右递归
			mergeSort(data,mid+1,end);
			//合并数组
			mergeArray(data,start,mid,end);
		}
		return data;
	}

运行测试：

// 归并排序算法测试
	public static void main(String[] args) {
		int[] data = new int[] {9,4,6,8,7,1};
		SortSuanFa sf = new SortSuanFa();
		data = sf.mergeSort(data, 0, data.length-1);
		System.out.println(Arrays.toString(data));
	}

运行结果：
[1, 4, 6, 7, 8, 9]