归并排序

一、归并排序原理

 归并排序(MERGE-SORT)简单来说就是将大的序列先视为若干个比较小的数组，分成几个比较小的结构，然后是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分就是将问题分(divide)成一些小的问题分别求解，而治(conquer).则将分的阶段得到的各答案"合"在一起)。

 可以看到这种结构很像两棵套在一起的满二叉树。分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。就是图中上面侧的满二叉树。
 再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，就是下侧的满二叉树。比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，这个操作与合并两个有序数组的完全一样，不同的是这里是将数组的两个部分合并。
 再看一下遍历时处理元素的过程：

二、代码实现

static void mergeSort(int[] array,int start,int end,int temp[]){if (start > end){return;}mergeSort(array,start,(start+end)/2,temp);mergeSort(array,(start+end)/2 + 1,end,temp);merge(array,start,end,temp);static void merge(int[] array,int start,int end,int[] temp){int middle = (start + end)/2;int left = start;int right = middle + 1;int index = left;while(left <= middle && right <= end){if (array[left] < array[right]){temp[index++] = array[left++];}else{temp [index++] = array[right++];}}while (left <= middle){temp[index++] = array[left++];}while (right <= end){temp[index++] = array[right++];for (int i = start; i <= end;i++){array[i] = temp[i];}}//测试方法public static void main(String[]args){int[] array = {6,3,2,1,4,5,8,7};int[]temp = new int[array.length];mergeSort(array,0,array.length - 1,temp);System.out.println(Arrays.toString(array));}