排序算法之归并排序 原理及java实现

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
一、原理
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现。

1.首先考虑“治”部分：如何将将二个有序数列合并。
这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数(可以通过指针移动来实现)。
然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
合并有序数列的效率是比较高的，可以达到O(n)。
2.解决了上面的合并有序数列问题，再来看“分”部分。
基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。那么如何让这二组组内数据有序？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。
分阶段可以理解为就是递归拆分子序列的过程，递归深度为log n。

这样通过先递归的分解数列，再合并数列就完成了归并排序。
归并排序的效率是比较高的，
设数列长为N，将数列分开成小数列一共要log N步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N log N)。
因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N log N)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

二、java代码实现

package sort;

import java.util.Arrays;

public class MergeSort {

	public static void sort(int[] arr) {
		int[] temp = new int[arr.length];
		//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
		sort(arr,0,arr.length-1,temp);
	}
	
	public static void sort(int[] arr,int start,int end,int[] temp) {
		if(start<end) {
			int mid =(end+start)/2;
			sort(arr,start,mid,temp);//左边归并排序，使得左子序列有序
			sort(arr,mid+1,end,temp);//右边归并排序，使得右子序列有序
			merge(arr,start,mid,end,temp);//将两个有序子数组合并操作
		}
	}
	
	//将两个有序数列arr[start,...,mid]和arr[mid+1,...,end]合并
	public static void merge(int[] arr,int start,int mid,int end,int[] temp) {
		int i =start;//左序列指针
		int j =mid+1;//右序列指针
		int k =0;//临时数组指针
		
		while(i<=mid&&j<=end) {
			if(arr[i]<=arr[j])//从小到大排列
				temp[k++]=arr[i++];
			else
				temp[k++]=arr[j++];
		}
		
		while(i<=mid){//如果左边剩余，将左边剩余元素填充进temp中
			temp[k++] = arr[i++];
		}
		
		while(j<=end) {//如果右边剩余，将右序列剩余元素填充进temp中
			temp[k++] = arr[j++];
		}
		
		k=0;
		while(start<=end) {  
			//将temp中当前操作的部分元素（已排序）拷贝到原数组中，覆盖arr[left,...,right]这部分数据。
			arr[start++] = temp[k++];
		}
		
	}
	
	
	public static void main(String[] args) {
		int[] a = new int[]{3,22,5,6,1,8,10,34,5,2};
		sort(a);
		System.out.println(Arrays.toString(a));
	}
}

执行结果
[1, 2, 3, 5, 5, 6, 8, 10, 22, 34]

注：有的书上是在merge()合并有序数列时分配临时数组，但是过多的new操作会非常费时。
因此只在sort()中new一个数组temp。后面的操作都共用这一个数组temp。

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log n|。总的平均时间复杂度为O(nlog n)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlog n)。

本文内容参考下面文章汇总写成，侵删。
[1] 作者： dreamcatcher-cx
出处： http://www.cnblogs.com/chengxiao/
[2]作者：MoreWindows 出处：https://blog.csdn.net/MoreWindows/article/details/6678165?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task