[数据结构与算法]归并排序思想与模板分析【排序算法篇】

主要思想：分治+合并

• 合并两个有序数组为一个有序数组是一个非常容易的操作，我们基于此操作做以下处理。

1. 通过分治法，将原数组分出许多长度为2的数组
2. 在这些长度为2的数组中，我们将第一个数看作为一个有序数组，第二个数也看作为一个有序数组，将它们进行合并，很容易合并为一个有序数组，那么现在这些长度为2的数组也都是有序数组了。
3. 递归回来，我们将原数组分为了长度为4的数组，在这些数组的内部，分别有两个有序数组，将它们进行合并，那么这些长度为4发数组也都是有序数组了。
4. 如此类推……
5. 我们最终可使原数组变为有序数组。

图解

取自网络

代码模板

public void get() {
    int[] arr = new int[]{3, 4, 5, 1, 2, -1, 0, 9, 4};
    mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
    for (int i : arr) {
        System.out.println(i);
    }
}

/**
 * 分治：分出子序列，结合下面的合并函数组合为一个归并算法
 *
 * @param arr   原数组
 * @param left  数组中第一个区间的第一个元素的下标
 * @param right 数组中第二个区间的最后一个元素的下标
 * @param tmp   辅助数组
 */
public void mergeSort(int[] arr, int left, int right, int[] tmp) {
    if (left < right) {
        //通过left、mid、right可将数组分为两个区间
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid, tmp);
        mergeSort(arr, mid + 1, right, tmp);
        //合并数组
        mergeArray(arr, left, mid, right, tmp);
    }
}


/**
 * 归并操作：将两个有序数组，合成一个辅助数组。 注意：辅助数组必须有序。
 * 最后将辅助数组替换原数组
 * <p>
 * 重点：虽说是合并两个有序数组，但实际上处理的是原数组的两个区间之间的合并
 * 你看我们传入的参数，并不是两个有序数组，而是原数组，和两个区间的位置（由left，mid，right可以确定）
 *
 * @param arr   原数组
 * @param left  第一个有序数组的第一个元素在arr中的位置
 * @param mid   第一个有序数组的最后一个元素在arr中的位置
 * @param right 第二个有序数组的最后一个元素在arr中的位置
 * @param tmp   辅助数组
 */
public void mergeArray(int[] arr, int left, int mid, int right, int[] tmp) {

    int i = left, k = mid + 1;
    int n = 0;
    //合成一个辅助数组，并保持辅助数组有序
    while (i <= mid && k <= right) {
        if (arr[i] < arr[k]) {
            tmp[n] = arr[i];
            i++;
        } else {
            tmp[n] = arr[k];
            k++;
        }
        n++;
    }
    /*
        以下两个whlie,只会有一个生效，目的是将数组中剩余的数输入至辅助数组
     */
    while (i <= mid) {
        tmp[n] = arr[i];
        n++;
        i++;
    }
    while (k <= right) {
        tmp[n] = arr[k];
        n++;
        k++;
    }
    //辅助数组替换原数组，注意位置
    for (int i1 = left; i1 <= right; i1++) {
        arr[i1] = tmp[i1 - left];
    }

    //除了上面的利用for循环替换原数组，也可以用jdk自带的api
    //System.arraycopy(tmp, 0, arr, left, right + 1 - left);
}

$归并排序：时间复杂度O(nlogn)、空间复杂度O(n)$