Java 归并排序_归并排序 java

归并排序

原理

1.把数组从中间划分成两个子数组;
2.一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素
3.依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。

时间复杂度

O(nlogn),稳定性看比较大小时是否加=

API模板

package DataStructureAndAlgorithm.Sort.HartSort;

/**
 * 归并排序
 */
public class Merge {
    private static Comparable[] assist;
    //对外的整体排序
    public static void sort(Comparable[] c){
        assist=new Comparable[c.length];//辅助数组
        sort(c,0,c.length-1);

    }
    //内部分段排序,从索引low到索引high的排序，采用递归分治
    private static void sort(Comparable[] c,int low,int high){
        //划分到直至不可再分
        if(low>=high) return;

        int mid=low+(high-low)/2;//中间位置

        sort(c,low,mid);
        sort(c,mid+1,high);

        merge(c,low,mid,high);
    }
    //将分段排序好的数组整合成一个数组
    private static void merge(Comparable[] c,int low,int mid,int high){
        //辅助数组指针
        int i=low;
        //两个子组的指针
        int lo = low;
        int hi= mid+1;
        while (lo<=mid&&hi<=high){
            //选取两个子组元素的较小值存入辅助数组
            if(greater(c[lo],c[hi])){
                assist[i++]=c[hi++];
            }else{
                assist[i++]=c[lo++];
            }
        }
        //lo子组没有遍历完
        while (lo<=mid){
            assist[i++]=c[lo++];
        }
        //hi子组没有遍历完
        while (hi<=high){
            assist[i++]=c[hi++];
        }
        //将辅助数组已经排好序的子组复制到原数组
        for (int j = low; j <=high ; j++) {
            c[j] = assist[j];
        }
    }


    //判断前者是否大于后者
    private static boolean greater(Comparable c1 ,Comparable c2){
        return c1.compareTo(c2)>0;
    }
}

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