从小到大排列

基本思想:

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

简单理解为: 使用递归的方法, 将一个数组平均分为两组, 两组, 两组....最后将每一组排序后合并

给定一个数组:

一层层分解后合并

对于每一组的数据每次分解后选择相应的start, end, mid进行拆分, 什么时候停止呢? 当start >= end时停止开始递归中的" 归 "的操作, 这个操作中需要对数组进行排列.如何进行排列呢? 通过数组的下表进行排列

 就以上图的第三行数据到第二行数据的左半部分为例进行说明:当" 归 "到第二行数据如图:

第三层完成递归后,将第三层右边的数和第三层左边的数作比较, 两边的数据放到一个大小为4个数据的新数组中.

让s1和s2作比较,  谁小先入数组中, 如图s2小放入后, s2++, 再让s1和e2比较,s1小放入后s1++, 再让e1和e2比较, e2小放入数组中, s2++因为s2大于e2, 停止比较, e1的值放入数组中.

代码展示:

   /*** 归并排序* @param array*/public static void mergeSort(int[] array) {mergeSortFun(array, 0, array.length-1);}private static void mergeSortFun(int[] array, int start, int end) {if (start >= end) {return;}int mid = (start+end)/2;mergeSortFun(array, start, mid);mergeSortFun(array, mid+1, end);merge(array, start, mid, end);}private static void merge(int[] array, int start, int mid, int end) {int s1 = start;int e1 = mid;int s2 = mid+1;int e2 = end;int[] tmpArr = new int[end-start + 1];int k = 0;while(s1 <= e1 && s2 <= e2) {if(array[s1] <= array[s2]) {tmpArr[k++] = array[s1++];}else{tmpArr[k++] = array[s2++];}}while(s1 <= e1) {tmpArr[k++] = array[s1++];}while(s2 <= e2) {tmpArr[k++] = array[s2++];}for(int i = 0; i < tmpArr.length; i++) {array[i+start] = tmpArr[i];}}

注意: 当进行右边的数据的传输时, tmpArr的下标从0开始, 而array的下标, 从0+start开始.