排序算法第三谈：归并排序-蒲公英云

排序算法第三谈：归并排序

小灰灰 2023-01-02 01:17 222阅读 0赞

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

思想:

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

分解：将n个元素分成个含n/2个元素的子序列。
解决：用合并排序法对两个子序列递归的排序。
合并：合并两个已排序的子序列已得到排序结果。

/** * @param arr 原数组 * @param left 左端索引 * @param right 右端索引 * @param temp 拷贝数组 */
    public static void mergeSort(int[] arr, int left, int right, int[] temp) { 
        if (left < right) { 
            //分
            int point = (left + right) / 2;
            mergeSort(arr, left, point, temp);
            mergeSort(arr, point + 1, right, temp);
            //合并
            merge(arr, left, point, right, temp);
        }
    }
    /** * 合并 * * @param arr 原数组 * @param left 左端索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 拷贝数组 */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) { 
        //从左往右依次合并
        int l = left;
        int r = mid + 1;
        int t = 0;//temp数组的索引
        while (l <= mid && r <= right) { //只有两端数据都没有合并，才逐个进行合并
            if (arr[l] <= arr[r]) temp[t++] = arr[l++];
            else temp[t++] = arr[r++];
        }
        //如果左端没有遍历完成
        while (l <= mid) { 
            temp[t++] = arr[l++];
        }
        //如果右边没有遍历完成
        while (r <= right) { 
            temp[t++] = arr[r++];
        }
        //拷贝回原数组,不是拷贝所有位置，只有复制的这一段需要拷贝
        int tempLeft = left;//当前合并的元素最左边的位置
        t = 0;
        while (tempLeft <= right) { 
            arr[tempLeft++] = temp[t++];
        }
    }