一头扎进算法导论-归并排序-蒲公英云

一头扎进算法导论-归并排序

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

用自己的话说：使用递归，把一数组分为两个子数组，再分为四个子数组…，直到子数组的个数为2时开始层层向上归并，最后得到排序好的数组

过程：
这里写图片描述

代码：

public int[] sort(int[] a,int start,int end){
   //输入开始坐标从0开始，和结束坐标
        int mid = (start+end)/2;//求中间坐标,奇数则取中间，偶数则取中间两个小的那个的坐标
        if(start<end){
   //如果开始坐标小于结束坐标，开始递归
            sort(a, start, mid);//从开始到中间
            sort(a, mid+1, end);//从中间右边一个开始到结束
            merger(a,start,mid,end);//归并
        }
        return a;
    }
    private void merger(int[] a, int start, int mid, int end) {
   //开始坐标，中间坐标，结束坐标
        int l = start;//左边开始坐标
        int r = mid+1;//右边开始坐标
        int[] temp = new int[end-start+1];//定义一个缓存数组
        int tk = 0;//指向缓存数组的当前坐标
        while(l<=mid&&r<=end){
   //开始判断，左边或者右边一边遍历完了就退出
            if(a[l]<a[r]){
                temp[tk] = a[l];//小的进入数组
                tk++;
                l++;
            }else{
                temp[tk] = a[r];
                tk++;
                r++;
            }
        }
        //把另一方未遍历的进行遍历填充
        while(l<=mid){
            temp[tk] = a[l];
            tk++;
            l++;
        }
        while(r<=end){
            temp[tk] = a[r];
            tk++;
            r++;
        }
        System.out.println("before merger :" + Arrays.toString(a));
        System.out.println("temp array :" + Arrays.toString(temp));
        //把遍历好的数组放进原数组
        for(int i=0;i<temp.length;i++){
            a[i+start] = temp[i];
        }
        System.out.println("after merger :" + Arrays.toString(a));
        System.out.println("--------------------------");
    }

测试：

public static void main(String[] args){
        int[] a= new int[]{
   5,8,3,4,7,2,7,4};
        a = new Merger().sort(a, 0, a.length-1);
        for(int i : a){
            System.out.print(i+",");
        }
    }

结果：

before merger :[5, 8, 3, 4, 7, 2, 7, 4]
temp array :[5, 8]
after merger :[5, 8, 3, 4, 7, 2, 7, 4]
-------------------------- before merger :[5, 8, 3, 4, 7, 2, 7, 4] temp array :[3, 4] after merger :[5, 8, 3, 4, 7, 2, 7, 4] --------------------------
before merger :[5, 8, 3, 4, 7, 2, 7, 4]
temp array :[3, 4, 5, 8]
after merger :[3, 4, 5, 8, 7, 2, 7, 4]
-------------------------- before merger :[3, 4, 5, 8, 7, 2, 7, 4] temp array :[2, 7] after merger :[3, 4, 5, 8, 2, 7, 7, 4] --------------------------
before merger :[3, 4, 5, 8, 2, 7, 7, 4]
temp array :[4, 7]
after merger :[3, 4, 5, 8, 2, 7, 4, 7]
-------------------------- before merger :[3, 4, 5, 8, 2, 7, 4, 7] temp array :[2, 4, 7, 7] after merger :[3, 4, 5, 8, 2, 4, 7, 7] --------------------------
before merger :[3, 4, 5, 8, 2, 4, 7, 7]
temp array :[2, 3, 4, 4, 5, 7, 7, 8]
after merger :[2, 3, 4, 4, 5, 7, 7, 8]
-------------------------- 2,3,4,4,5,7,7,8,