排序之归并排序

前言

　　路漫漫其修远兮，吾将上下而求索！

　　github：https://github.com/youzhibing

　　码云(gitee)：https://gitee.com/youzhibing

基本思想

　　“归并”一词的中文含义就是合并、并入的意思，而在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表。既然是归并、并入，那么必然就有子序列了，子序列从何而来，当然是目标序列拆分而来啦！ 就是先拆分，在合并。
      归并排序（Merging Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归 并，得到?n/2?（?x?表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

　　其过程如图所示

代码实现

    public void mergeSort(int[] arr){
		mSort(arr,0,arr.length-1);
	}

	/**
	 * 先拆分，再归并
	 * @param arr
	 * @param min
	 * @param max
	 */
	private void mSort(int[] arr, int min, int max) {
		int mid = (min + max) / 2;
		if(min < max){
			mSort(arr,min,mid);			// 拆分arr[min...mid]
			mSort(arr,mid+1,max);		// 拆分arr[mid+1...max]
			merge(arr,min,mid,max);		// 归并有序序列arr[min...mid]和有序序列arr[mid+1...max]
		}
	}

	/**
	 * 归并arr[min...mid]和arr[mid+1...max]
	 * 此时arr[min...mid] arr[mid+1...max]分别有序
	 * @param arr
	 * @param min
	 * @param mid
	 * @param max
	 */
	private void merge(int[] arr, int min, int mid, int max) {
		int[] tarr = new int[max+1];
		int i=min,j=mid+1,tIndex=min;
		// 将arr[min...mid]与arr[mid+1...max]中元素从小到大逐个赋值到tarr数组中
		while(i<=mid && j<=max){
			if(arr[i] < arr[j]){
				tarr[tIndex++] = arr[i++];
			} else {
				tarr[tIndex++] = arr[j++];
			}
		}
		// arr[min...mid]中元素已经全部赋值到tarr中，将arr[mid+1...max]剩余的元素赋值到tarr中
		if(i>mid){
			while(j<=max){
				tarr[tIndex++] = arr[j++];
			}
		}
		// arr[mid+1...max]中元素已经全部赋值到tarr中，将arr[min...mid]剩余的元素赋值到tarr中
		if(j>max){
			while(i<=mid){
				tarr[tIndex++] = arr[i++];
			}
		}
		//将临时数组tarr中有序序列赋值到目标数组arr中，使之arr[min...max]有序
		for(int k=min; k<=max; k++){
			arr[k] = tarr[k];
		}
	}

执行过程模拟

　　其实上图已经模拟出来整个程序的执行过程，先进行拆分，然后归并，代码中注释也已经写的很清楚了，具体的模拟过程就博主就不演示了，不清楚的就请自己根据代码进行模拟了。

总结

　　其实思想是比较好理解的，实现也不是那么难，最难的其实是光说不练、不去实现，总认为理解思想就够了，可结果是当你真正去实现的时候你发现并不是那么的容易；理解别人的思路、融入自己的理解、付之实践（代码实现）、实践优化，最终完全理解！