归并排序

一、概念

归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

二、思路

先拆分，再合并，在合并的过程中结束临时空间进行排序。

拆分：从中间位置拆开，数据分成左右两部分，继续进行拆分，直到数据拆分成一个一个的时候停止。

向左拆分：right = mid   (/mid-1)   

向右拆分：left = mid+1  (/mid)

eg:

合并有序序列：

两个序列定义两个指针，分别指向有序序列的第一个值，比较两指针指向的数据大小，把大的一方放到新的空间中。

---

三、时间复杂度 

在上述例子中（5，7，4，2，0，3，1，6）

第一层   1   2^0

第二层   2   2^1

第三层   4  2^2

第四层   8   2^3

第k层  2^(k-1） =x

k=log2x      O(nlogn)

---

四、代码

递归结束出口：left==right

else

向左拆分：  f(arr,left,right)= f(arr,left,mid)

向右拆分：  f(arr,left,right)= f(arr,mid+1,right)

package com.lojarro.排序;

import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int[] arr= {12,3,32,11,-1,33,11,123,12,56};
		mergeSort(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	//拆分
	public static void mergeSort(int[] arr, int left, int right) {
		//递归出口
		if(left==right) {
			return;
		}
		int mid=(left+right)/2;
		//向左拆分
		mergeSort(arr,left,mid);
		//向右拆分
		mergeSort(arr,mid+1,right);
		
		//合并
		merge(arr,left,right,mid);
	}
	public static void merge(int[] arr,int left,int right,int mid) {
		//定义第一段和第二段的开始
		int s1=left;
		int s2=mid+1;
		//定义临时空间
		int[] temp =new int[right-left+1];
		int index=0;//定义游标遍历临时空间
		//判断s1和s2指向的数据大小，将其存入临时数组
		while(s1<=mid&&s2<=right) {
			if(arr[s1]<arr[s2]) {
				temp[index]=arr[s1];
				s1++;
				index++;
			}else {
				temp[index]=arr[s2];
				s2++;
				index++;
			}
		}
		//判断s1中是否有数据，如果有将其放入临时数组当中
		while(s1<=mid) {
			temp[index]=arr[s1];
			s1++;
			index++;
		}
		//判断s2中是否有数据，如果有将其放入临时数组当中
		while(s2<=right) {
			temp[index]=arr[s2];
			s2++;
			index++;
		}
		//将临时数组中的数据写回原数组
		for(int i=0;i<temp.length;i++) {
			arr[left+i] = temp[i];
		}
	}
}