归并排序详解

归并排序详解

说明

1. 归并排序使用分治的思想,分治是将一个复杂的问题拆结尾简单的问题，然后使用递归的思路求解
2. 归并实质上是将数组中的元素先二分，第一次从中间分成两部分，然后对这两部分再二分，依次进行，直到分成的每组只有一个元素，如果只有一个元素，那么就一定能保证这组元素是有序的，分解结束后，将分解后的每组元素进行合并
3. 合并需要开辟额外的空间，典型的以空间换时间的思想，需要创建一个和原数组等大小的临时数组用于排序
4. 将两组分好的元素依次比较大小，将小的元素放到临时数组的前边，，大的元素放到临时数组的后边，依次进行，直到将最后一组元素也进行过比较
5. 最后将临时数组中的元素拷贝到原数组中，完成排序
6. 源码及详解见下

源码及分析

/**
     * 归并排序
     * 分 + 和
     *
     * @param arr   要排序的数组
     * @param left  数组左边索引
     * @param right 数组右边索引
     * @param tmp   临时数组
     */
    public static void mergeSort(int[] arr, int left, int right, int[] tmp) {
        //左侧索引小于右侧 则二分
        if (left < right) {
            //记录中间索引
            int mid = (left + right) / 2;
            //向左递归分解
            mergeSort(arr, left, mid, tmp);
            //向右递归分解
            mergeSort(arr, mid + 1, right, tmp);
            //合并
            merge(arr, left, mid, right, tmp);
        }
    }

    /**
     * 归并排序之并，核心思想为分治，及先分再治
     *
     * @param arr   要排序的数组
     * @param left  要合并的数组左侧索引
     * @param mid   中间索引
     * @param right 右侧索引
     * @param temp  临时数组,用来临时保存排好序的数字
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        //定义变量 i 保存左侧有序数组的初始索引
        int i = left;
        //定义变量 j 保存右侧有序数组的初始索引
        int j = mid + 1;
        //定义变量 tmp 指向临时数组的初始索引
        int tmp = 0;
        //先将左侧数组和右侧数组中的元素按照大小存储到集合中,直到一侧元素全部移动到临时数组中
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[tmp] = arr[i];
                i++;
                tmp++;
            } else {
                temp[tmp] = arr[j];
                j++;
                tmp++;
            }
        }
        //则循环结束后一侧的数组全部移动到临时数组中
        //然后再将另一侧剩余的数字移动到临时数组中
        while (i <= mid) {
            temp[tmp] = arr[i];
            i++;
            tmp++;
        }
        while (j <= right) {
            temp[tmp] = arr[j];
            j++;
            tmp++;
        }
        //则左右两侧的元素按照大小全部移动到临时数组中
        //再将临时数组中的元素拷贝到原始数组中，注意并不是全部拷贝
        //临时数组索引置为0
        tmp = 0;
        //定义临时变量tmpLeft
        int tmpLeft = left;
        //循环拷贝，将当前排好序的元素拷贝到arr
        while (tmpLeft <= right) {
            arr[tmpLeft] = temp[tmp];
            tmp++;
            tmpLeft++;
        }
    }

原文：https://www.cnblogs.com/mx-info/p/14841664.html