归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

算法步骤

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4.重复步骤 3 直到某一指针达到序列尾；
5.将另一序列剩下的所有元素直接复制到合并序列尾。

动图演示

mergeSort.gif

复杂度

时间复杂度 = O(n*lgn) 空间复杂度 = O(n）

代码实现

归并算法 bottom-Up

public class MergeSortTestD {

    public static void main(String[] args) {
        int[] arr = RandomUtils.getRandomIntegerArray(20);
        mergeSort(arr);

    }

    public static void mergeSort(int[] arr) {
        int step = 1;
        int high = arr.length;
        int low = 0;
        while (step < high) {
            for (int i = low; i < high; i += step << 1) {
                int lo = i, hi = (i + (step << 1)) <= high ? (i + (step << 1)) : high; //定义二路归并的上界与下界
                int mid = i + step <= high ? (i + step) : high;
                mergeSortAcs(arr, lo, mid, hi);
            }

            //将i和i+step这两个有序序列进行合并
            //序列长度为step
            //当i以后的长度小于或者等于step时，退出
            step <<= 1;//在按某一步长归并序列之后，步长加倍
        }
 }



    public static void mergeSortAcs(int[] num,int start,int middle,int end) {

        if (end - start < 2 || middle <= start || end <= middle) {

            return ;
        }

        int len1 = middle - start + 1;
        int len2 = end - middle + 1;
        int max = len1 > len2?len1: len2;

        int[] num1 = new int[len1];
        int[] num2 = new int[len2];


        for (int i = 0; i < max; i++) {
            if (i < len1) {
                num1[i] = num[i + start];
            }
            
            if (i < len2 && i + middle < end) {
                num2[i] = num[i + middle];
            }
        }

        num1[len1 - 1] = Integer.MAX_VALUE;
        num2[len2 - 1] = Integer.MAX_VALUE;

        int p = 0,q = 0;
        for (int i = start; i < end; i++) {
            if (num1[p] < num2[q]) {
                num[i] = num1[p];
                p++;
            } else {
                num[i] = num2[q];
                q++;
            }
        }

    }
}

归并算法 top-down

public class MergeSortTestA {

    public static void main(String[] args) {

        int[] arr = RandomUtils.getRandomIntegerArray(15);

        mergeSort(arr,0,arr.length - 1);
    }

    public static void mergeSort(int[] arr,int start,int end) {
        if (start < end) {
            int middle = (end + start) / 2;

            mergeSort(arr,start,middle);
            mergeSort(arr,middle + 1,end);

            mergeSortAsc(arr,start,middle,end);
        }
    }


    public static void mergeSortAsc(int[] arr,int start,int middle,int end) {
        int left = middle - start + 1;
        int right = end - middle;
        int maxSize = left > right?left:right;
        int[] arrLeft = new int[left + 1];
        int[] arrRight = new int[right + 1];


        for (int i = 0; i < maxSize; i++) {
            if (i < left) {
                arrLeft[i] = arr[i + start];
            }

            if (i < right) {
                arrRight[i] = arr[middle + i + 1];
            }
        }

        arrLeft[left] = Integer.MAX_VALUE;
        arrRight[right] = Integer.MAX_VALUE;

        int p = 0,q = 0;
        for (int i = start; i < end; i++) {
            if (arrLeft[p] < arrRight[q]) {
                arr[i] = arrLeft[p];
                p++;
            }else {
                arr[i] = arrRight[q];
                q++;
            }
        }
    }
}