归并排序java版

好长时间没写过归并排序，在学习并发中又遇到了一个归并排序的demo，于是就想试试自己还能不能写出来，结果没写出来…，看了一些文章后，整理了一下思路，把归并排序写了出来，在这里自己分析一下，加强记忆。

归并排序的思想是分而治之，总之就是拆分，拆分，再拆分，将粒度降到最低，然后再进行合并，合并，再合并。

转载部分图片从外部：

拆分图解：

通过看临时数组，将源数据左右部分放到临时数组；
使用i,j两个索引控制索引位；
当i<j位的数据，则把i位放入temp，否则将j位数据放入temp，并将对应索引+1；
最后将当一侧索引达到尽头，另一侧数据由于已经有了顺序，则直接全部放入temp中即可；

直接贴代码：

public class MergeSortDemo {public  static void merge(int[] arr, int left, int right, int[] temp){// int mid =   (left+right)/2;int mid =   left+(right-left)/2;int i=left;int j = mid+1;int index = left;//当l小于等于中间点，j小于等于右索引//只有满足以下两个条件才能进行循环//下面的操作是以左右两边的同时向右推进，//左侧的数值小则将左侧的索引位数值放到temp[index]中，同时左索引+1，index+1;//右侧的数值小则将右侧的索引位数值放到temp[index]中，同时右索引+1,index+1;while (i<=mid && j <=right ){if(arr[i]<arr[j]){temp[index++] = arr[i++];}else {temp[index++] = arr[j++];}}//当条件不满足时，必须是i>mid或j>right才会不满足；//此时由于排序，左侧数据的右端大于左端（拆分后的数据经过排序各部分已经具有顺序）；////一旦i>mid，则代表左侧全部放到temp中，也代表左侧数据较小，全部小于右侧剩余的数据，右侧剩余的数据已经具有顺序，则可以直接添加到temp后尾；//将剩余的数据放到temp中，//下面两个while只能满足其一；while (i<=mid){temp[index++] = arr[i++];}while (j<=right){temp[index++] = arr[j++];}//再将数据回填到arr中；i=left;j=left;//只把左右索引这部分数据进行回填，while (i<=right){arr[i++]=temp[j++];}}/**** @param arr 源数组* @param left 左索引* @param right 右索引* @param temp 临时数组*/public static void sort(int arr[],int left,int right,int temp[]){//如果左索引小于右索引，则排序if(left<right){//左排序，每次折半排序，从左索引，到中间点；sort(arr,left,left+(right-left)/2,temp);//右排序，从中间点+1，到右索引，由于上边排序包含中间点，所以下面的必须中间点+1;sort(arr,left+(right-left)/2+1,right,temp);//合并merge(arr,left,right,temp);}}public static void main(String[] args) {int arr[]=new int[]{1,9,7,10,8,14,3,5,2,6,78,16,78,88};int arr2[]=new int[arr.length];sort(arr,0,arr.length-1,arr2);for (int i : arr) {System.out.println(i);}}
}

文中图片来源于外链

外链参考文章地址:
点击跳转