【排序算法（五）】归并排序

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分治算法的一般步骤：

（1）分解，将要解决的问题划分成若干规模较小的同类问题；

（2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

分而治之

合并相邻有序子序列
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

Java版本实现

package sort;

public class MergeSort<T extends Comparable<? super T> > {
	
	T[] a = null;
	
	public MergeSort(T a[]) {
		this.a = a ;
	}
	
	public void mergeSort() {
		Object[] temp = new Object[a.length]; 
		sort(a , 0 , a.length - 1 , temp);
	}
	
	private void sort ( T[] a , int left , int right ,Object[] temp ) {
		if(left == right) {
			return;
		}else {
			int mid = (left + right) / 2;
			sort( a , left , mid , temp);
			sort( a , mid + 1 , right , temp);
			merge( a , left , mid , right , temp );
			display();
		}
	}
	
	private void merge( T[] a , int left , int mid , int right , Object[] temp) {
		
		int i = left ;//左序列指针
		int j = mid + 1 ;//右序列指针
		int t = 0 ;//临时数组指针
		
		while(i < mid + 1 && j < right + 1) {
			
			if(a[i].compareTo(a[j]) < 0) {
				temp[t ++] = a[i ++];
			}else {
				temp[t ++] = a[j ++] ;
			}
		}
		
		while(i < mid + 1) {
			temp[t ++] = a[i ++];
		}
		
		while(j < right + 1 ) {
			temp[t ++] = a[j ++]; 
		}
		
		t = 0;
		while(left < right + 1) {
			a[left ++] = (T) temp[t ++];
			
		}
		
	}
	 
	public void display() {
		for(int i = 0 ; i < a.length ; i ++)
			System.out.print(a[i] + " ");
		System.out.println();
	}
	
	public static void main(String[] args) {
		
		Integer a[] = {10 , 2 , 8 , 3 , 5 , 7 , 6 , 1 , 4};
		MergeSort<Integer> ms = new MergeSort<>(a);
		System.out.print("排序前:");
		ms.display();
		ms.mergeSort();
		System.out.print("排序后:");
		ms.display();
	}
}

算法分析：

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