【高级排序】之归并排序

Myth丶恋晨 2022-02-03 08:19 221阅读 0赞

### 算法评价： ###

*  **时间复杂度：![20190511093749312.png][]。**
 *  **空间复杂度：![20190509005213845.png][]**。
 *  **稳定性：稳定。**
 *  **适用数据规模量：大规模。**

**算法复杂度与数据规模量关系图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70][]

### 算法说明： ###

如下图所示，先将待排序数组进行拆分(拆分规则多样，下图为二分法)，然后再将拆分开的各个子元素进行归并(归并方式多样，下图为两路归并)，得到多个小的有序的数组集合，然后再将各个有序的小数组集合归并……最终得到有序数组集合。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 1][]

### 算法演示图： ###

![20190509005332903.gif][]

注：此动图中采用**前序遍历**的方式进行归并。

### Java对归并排序的实现： ###

/**
     * 归并排序的Java实现
     *
     * @author JustryDeng
     * @date 2019/5/6 18:38
     */
    public class Merge {
    
        /**
         * 归并排序的java实现
         *
         * @param originArray
         *            要被排序的元素集合
         * @param asc
         *            升序/降序。 true-升序; false-降序
         *
         * @date 2019/5/6 18:40
         */
        public static void sort(int[] originArray, boolean asc) {
            if (originArray == null || originArray.length <= 1) {
                return;
            }
            // 数组最左边元素的索引
            int left = 0;
            // 数组最右边元素的索引
            int right = originArray.length - 1;
            splitAndMerge(originArray, left, right, asc);
        }
    
    
        /**
         * (两路)拆分、归并 数组
         *
         * @param originArray
         *            数组
         * @param left
         *            数组的起始元素索引
         * @param right
         *            数组的结尾元素索引
         * @param asc
         *            升序/降序。 true-升序; false-降序
         * @date 2019/5/8 23:06
         */
        private static void splitAndMerge(int[] originArray, int left, int right, boolean asc) {
            // 中间那个数的索引
            int center = (left + right) / 2;
            /*
             * 当目标区域要只有一个元素时，不再进行拆分
             *
             * 已知originArray长度大于0, 这里简单数学证明: 当center = right时，originArray长度为1
             * ∵ center = (left + right) / 2 且 center = right
             * ∴ right = (left + right) / 2
             * ∴ 2 * right = left + right
             * ∴ right = left
             * ∴ right = left
             * ∴ originArray长度为1
             */
            if (center == right) {
                return;
            }
            // 二叉树【前序遍历】, 再次进行拆分
            splitAndMerge(originArray, left, center, asc);
            splitAndMerge(originArray, center + 1, right, asc);
            // 合并
            merge(originArray, left, center, right, asc);
        }
    
        /**
         * 归并两个有序的数组
         *
         * @param originArray
         *            数组。 注:该数组由两个紧邻的 有序数组组成
         * @param left
         *            要归并的第一个数组的起始元素索引
         * @param center
         *            要归并的第一个数组的结尾元素索引
         * @param right
         *            要归并的第二个数组的结尾元素索引
         *            注:要合并的第二个数组的结尾元素索引为center + 1
         * @param asc
         *            升序/降序。 true-升序; false-降序
         * @date 2019/5/8 23:06
         */
        private static void merge(int[] originArray, int left, int center, int right, boolean asc) {
            int[] tmpArray = new int[right - left + 1];
            int i = left, j = center + 1, tmpIndex = 0;
            // 循环比较， 直至其中一个数组所有元素 拷贝至 tmpArray
            while (i <= center && j <= right) {
                // 控制升序降序
                boolean ascFlag = asc ? originArray[i] <= originArray[j] : originArray[i] >= originArray[j];
                if (ascFlag) {
                    tmpArray[tmpIndex] = originArray[i];
                    i++;
                    tmpIndex++;
                } else {
                    tmpArray[tmpIndex] = originArray[j];
                    j++;
                    tmpIndex++;
                }
            }
            // 将剩余那个没拷贝完的数组中剩余的元素 拷贝至 tmpArray
            while (i <= center) {
                tmpArray[tmpIndex] = originArray[i];
                i++;
                tmpIndex++;
            }
            while (j <= right) {
                tmpArray[tmpIndex] = originArray[j];
                j++;
                tmpIndex++;
            }
            // 将临时数组中的元素按顺序拷贝至originArray
            System.arraycopy(tmpArray, 0, originArray, left, tmpArray.length);
        }
    
    }

### 测试一下： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 2][]

控制台输出：

![20190509005432329.png][]

**归并排序，学习完毕！**

### ^\_^ 如有不当之处，欢迎指正 ###

### ^\_^ 本文已被收录进《程序员成长笔记(五)》，笔者JustryDeng ###

[20190511093749312.png]: /images/20220203/1ceef4d8ab3641c388f01593443a96dc.png
[20190509005213845.png]: /images/20220203/bd2faba4d2dd49e7a7c71798688bfbbd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70]: /images/20220203/af02735ecba34de2af712b4cb0087e78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 1]: /images/20220203/1c3926833fce4b5d8c6e93f968c7669f.png
[20190509005332903.gif]: /images/20220203/b166f684f3a04770aeb7f45dac0f802a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 2]: /images/20220203/eeae4628331f40dfaa6a347a5fbbc54e.png
[20190509005432329.png]: /images/20220203/5f9501814f5249beb403606d72acf736.png