归并排序java版

归并排序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);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

文中图片来源于外链

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