归并排序.

归并排序介绍

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用金典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各个答案"修补"在一起,即分而治之)

归并排序的思想示意图1-基本思想

说明
可以看到这种结构很像一棵完全二叉树,本文的归并排序采用递归去实现,(也可以采用迭代的范式去实现)分阶段可以理解为就是递归查房子序列的过程.

归并排序思想示意图2,合并相邻有序子序列

再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并最终序列[1,2,3,4,5,6,7,8].来看下实现步骤

代码如下

package sort;

import java.util.Arrays;

public class MergetSort {
    public static void main(String[] args) {
     int[] arr={8,4,5,7,1,3,6,2};
     int[] temp=new int[arr.length];
     mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

//分+合的一个方法
    public static  void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid=(left+right)/2;//中间索引
            //向左递归进行分解
            mergeSort(arr,left,mid,temp);
            //向右递归进行分解
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }

    }


    //合并的方法.

    /**
     *
     * @param arr  排序的原始数组
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 做中转的数组
     */
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i=left;//初始化i.左边有序序列的初始化索引
        int j=mid+1;//初始化j.右边有序序列的初始化索引
        int t=0;//指向temp数组的当前索引

        //一
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列,有一边处理完为止

        while (i<=mid&&j<=right){
            //如果左边的有序序列的当前元素,小于等于右边有序序列当前元素
            //我们就把左边的当前元素拷贝到我们的temp数组
            //然后我们的t和i都后移一下
            if(arr[i]<=arr[j]){
                temp[t]=arr[i];
                t+=1;
                i+=1;
            }else {//反之,将右边有序序列当前元素填充都temp数组
                temp[t]=arr[j];
                t+=1;
                j+=1;
            }
        }
         //二
        //把有剩余数据的一遍全部填充到temp去
        while (i<=mid){ //说明我们的左边的有序序列还有剩余元素,全部填充到temp
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }
        while (j<=right){//说明我们的右边的有序序列还有剩余元素,全部填充到temp
         temp[t] =arr[j];
         t+=1;
         j+=1;
        }

        //三
        //将我们temp数组重写拷贝到arr
        //注意并不是每一次都拷贝所有
        t=0;
        int tempLeft=left;//
        System.out.println("tempLeft:"+tempLeft+"right=:"+right);
        while (tempLeft<=right){//
            arr[tempLeft]=temp[t];
            t+=1;
            tempLeft+=1;
        }
    }
}

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

我们归并排序的时间复杂度是比较小的.
**其实归并排序比较难以理解,我们如何分,如何合"这个思想的理解较难,代码看着没有什么感觉,但是先做一个了解把,大概知道,后面还要考自己多看,多理解,说不定那天就明白了.