归并排序 Merge Sort

将两个有序数列合并成一个有序数列，称之为归并。归并排序Merge Sort就是利用归并思想堆数列进行排序

1. 前言

根据具体的实现，归并排序包括：从上往下和从下往上两种方式

• 从下往上

  将带排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；的到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4有序数列，再将它们两两合并；直到合并成一个数列为止。

• 从上往下

  与从上往下在排序上是相反的，主要包括3步：

  • 分解：将当前区间一分为二，即求分裂点mid =（low+high)/2
  • 求解：递归地堆两个子区间a[low … mid]和a[min+1 … high]进行归并排序。递归的中介条件是子区间长度为1
  • 合并：将已排序的两个子区间a[low … mid]和a[min+1 … high]归并为一个有序的区间a[low … high]

  

2. 实现

2.1 从上往下的归并排序

从上往下的归并排序采用了递归的方式实现。它的原理非常简单，如下图:

2.2 从下往上的归并排序

从下往上的归并排序的思想正好与”从下往上的归并排序”相反。如下图:

3. 时间复杂度和稳定性

• 时间复杂度：O(N*logN)

  假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢? 归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(N*lgN)

• 稳定性：归并排序是稳定的算法，它满足稳定算法的定义

4. 代码实现

package org.example.sort;

/**
 * 归并排序
 *
 * @author xiaoyuge
 */
public class MergeSort {
    /**
     * 将一个数组中的两个相邻有序区间合并成一个
     *
     * @param a     包含两个有序区间的数组
     * @param start 第一个有序区间的起始位置
     * @param mid   第一个有序区间的结束位置，也是第二个有序区间的起始位置
     * @param end   第二个有序区间的结束位置
     */
    public static void merge(int[] a, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];//汇总两个有序区间的临时区域
        int i = start;  //第1个有序区间的索引
        int j = mid + 1;     //第2个有序区间的索引
        int k = 0;   //临时的索引

        while (i <= mid && j <= end) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        while (j <= end) {
            temp[k++] = a[j++];
        }
        //将排序后的元素，全部都整合到数组a中
        for (i = 0; i < k; i++) {
            a[start + i] = temp[i];
        }
        temp = null;
    }

    /**
     * 归并排序  从上往下
     *
     * @param a     待排序的数组
     * @param start 数组的起始位置
     * @param end   数组的结束位置
     */
    public static void mergeSortUpToDown(int[] a, int start, int end) {
        if (a == null || start >= end) {
            return;
        }
        int mid = (end + start) / 2;
        mergeSortUpToDown(a, start, mid);    //递归排序a[start...mid]
        mergeSortUpToDown(a, mid + 1, end);    //递归排序a[end...end]

        //将两个有序区间合并成一个
        merge(a, start, mid, end);
    }

    /**
     * 对数组a做若干次合并：数组a的总长度len,将它分成若干个长度为gap的子数组
     * 将每2个相邻的子数组进行合并排序
     *
     * @param a   待排序的数组
     * @param len 数组长度
     * @param gap 子数组的长度
     */
    public static void mergeGroups(int[] a, int len, int gap) {
        int i;
        int towLen = 2 * gap;   //相邻两个子数组的长度

        //合并
        for (i = 0; i + 2 * gap - 1 < len; i += (2 * gap)) {
            merge(a, i, i + gap - 1, i + 2 * gap - 1);
        }
        //若i+gap-1 < len -1则剩余一个子数组没有配对，将该子数组合并到已排序的数组中
        if (i + gap - 1 < len - 1) {
            merge(a, i, i + gap - 1, len - 1);
        }
    }

    /**
     * 归并排序   从下往上
     *
     * @param a 待排序的数组
     */
    public static void mergeSortDownToUp(int[] a) {
        if (a == null) {
            return;
        }
        for (int n = 1; n < a.length; n *= 2) {
            mergeGroups(a, a.length, n);
        }
    }

    public static void main(String[] args) {
        int[] a = {80,30,60,40,20,10,50,70};
        //从上往下
        mergeSortUpToDown(a, 0, a.length - 1);
        for (int i : a) {
            System.out.printf("%d ", i);
        }
    }
}