高级排序之 归并排序

　　归并排序

　　一、什么是归并排序?

　　以整个数组为对象执行mergeSort

　　mergeSort:

　　1.将给定的包含n个元素的局部数组分割成两个局部数组，

　　每个数组包含n/2个元素

　　2.对两个局部数组分别执行mergeSort排序

　　3.通过merge将两个已经排序完毕的局部数组“整合”成一个数

　　组

　　二、分析步骤

　　1.分割数组

　　在解释分割数组之前，我们不得不提一下分治法。

　　分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。

　　分治法的精髓：

　　分–将问题分解为规模更小的子问题;

　　治–将这些规模更小的子问题逐个击破;

　　合–将已解决的子问题合并，最终得出“母”问题的解;

　　简单的来说，分三步：

　　1.将问题“分割”

　　2.递归求解局部问题

　　3.整合，解决原问题

　　2.分别排序

　　这里我们用到递归，分别对分割后的两个数组进行排序

　　mergeSort(A,n,left,mid);

　　mergeSort(A,n,mid,right);

　　3.整合数组大连人流医院 http://mobile.84211111.cn/

　　这里在提一点，在递归时，一定要有结束条件，所以，这里给出merge进行递归结束。

　　void merge(int[] A,int n,int left,int mid,int right){

　　int n1 = mid - left;

　　int n2 = right - mid;

　　for (int i = 0; i < n1; i++) {

　　L[i] = A[left+i];

　　}

　　for (int i = 0; i < n2; i++) {

　　R[i] = A[mid+i];

　　}

　　L[n1] = R[n2] = SENTINEL;

　　int i = 0,j = 0;

　　for (int k = left; k < right; k++) {

　　cut++;

　　if (L[i]<=R[j])

　　A[k] = L[i++];

　　else

　　A[k] = R[j++];

　　}

　　}

　　总结

　　所谓的高等排序，都是将初等函数进行分割，在用分治的思想构建而成。