归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小问题然后递归求解，而治的阶段则将分的阶段得到的各个答案“修补”在一起）。

基本思想

将一个需要排序的数组通过递归进行拆分，当每一个元素都是一个个体的时候，再进行合并，合并时将合并的数据保存到一个临时开辟的空间中，这意味着需要额外的空间来保存数据；这个算法主要分为三步： （一）：拆分
将一个初始的数组递归拆分，将每一个元素拆分至单个个体独立存在（这里并不对数据进行操作） （二）：合并（核心） 将拆分的当个个体元素进行合并，合并的过程中进行排序，并保存到临时创建的空间内（需要对数据进行排序操作） （三）：拷贝
将临时空间内的数据拷贝到原数组中

合并的实现图解如下

代码实现

package com.ygl.sort;

import java.util.Arrays;
import java.util.Date;

/**
 * 归并排序算法
 * 
 * @author Administrator
 * 
 */
public class MergetSort {

	public static void main(String[] args) {
		int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 };
		mergeSort(arr, 0, arr.length-1,temp);
		System.out.println(Arrays.toString(arr));
	}

	/**
	 * 
	 * @param arr 原始数组
	 * @param left 左边的初始索引
	 * @param right	右边的初始索引
	 * @param temp 暂时保存数据的数组
	 */
	public static void mergeSort(int[] arr,int left,int right,int[] temp){
		if(left<right){
			//中间索引
			int mid = (left+right)/2;	
			//像左递归进行分解
			mergeSort(arr, left, mid, temp);
			//像右递归进行分解
			mergeSort(arr, mid+1, right, temp);
			//调用合并的方法
			merge(arr, left, mid, right, temp);
		}
	}
	
	/**
	 * 合并的方法
	 * @param arr 原始数组
	 * @param left 左边有序序列的初始索引
	 * @param mid 中间索引
	 * @param right 右边索引
	 * @param temp 暂时保存数据的数组
	 */
	private static void merge(int[] arr, int left, int mid, int right,
			int[] temp) {
		int i = left; // 初始化i，左边的有序序列的初始索引
		int j = mid + 1; // 初始化j，右边有序序列的初始索引
		int t = 0; // 指向temp数组的当前索引

		while (i <= mid && j <= right) {
			/*
			 * 如果左边的元素小于等于右边的元素，将左边的元素填充到temp数组中； 
			 * 反之将右边的元素填充到temp数组中
			 */
			if (arr[i] <= arr[j]) {
				temp[t] = arr[i];
				t += 1;
				i += 1;
			} else {
				temp[t] = arr[j];
				t += 1;
				j += 1;
			}
		}

		// 当左边的有序序列还有剩余元素，则全部填充到temp中
		while (i <= mid) {
			temp[t] = arr[i];
			t += 1;
			i += 1;
		}

		// 当右边的有序序列还有剩余元素，则全部填充到temp中
		while (j <= right) {
			temp[t] = arr[j];
			t += 1;
			j += 1;
		}

		//将temp数组的元素拷贝到arr(每一次合并都会拷贝)
		t = 0;
		int tempLeft = left;
		while (tempLeft <= right) {
			arr[tempLeft] = temp[t];
			t += 1;
			tempLeft += 1;
		}
	}
}

总结

归并算法的核心在于合并的过程，合并的次数为arr.length()-1次，因此时间复杂度表达式为O(n log n)，是一种线性对数阶，处理数据的时间相对快；