算法-合并排序

分手后的思念是犯贱 2023-10-05 19:16 10阅读 0赞

上周分析了[排序算法][Link 1]，这周分析合并排序算法。

**目录**

思想

画图分析

程序实现

思路

代码

--------------------

## 思想 ##

合并排序也是分治算法中的一种思想，将一组数组从中分成两组，再将两组各自从中分成四组，依次循环分组，直到每组只剩下单独的只包含一个数字的数组。之后再将各个数组依次按照大小排序合并成一组，就成为了有序的数组。

## 画图分析 ##

先展示分组，以长度为9的数组为例：\[9,5,2,7,12,4,3,1,11\]

![2021020514130557.png][]

先拆分数据：

1.取中间下标mid = (0+8)/2 = 4,因此分为两个数组：下标0~4,5~8两组。

![20210205141502785.png][]

2.分0~4下标的数组，mid=(0+4)/2=2，因此分为0~2,3~4两组

![20210205141619390.png][]

3.分0~2下标的数组，mid=(0+2)/2=1，因此分为0~1,2两组

![20210205141729256.png][]

4.分0~1下标的数组，mid=（0+1）/2 = 0,因此分为0,1两组

![20210205141812509.png][]

这样就将一个大数组分成了单个数字的数组，其余别的组合上述分组方法一致，分组挺简单的，数据太多了，我就不一一说明了。展示一下我分组过程

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70][]

注：可能有同学不明白为什么分组要是mid归到左边部分，而不是归到右边部分。我试了一下，你们一看大概也能明白为什么了，因为如果把mid归到后面，那么总是左边的优先独立成为一个数组，但是右边的因为数值比较大，但是下标又不符合mid的规则，因此可能出现不能分到单位为1的数组的情况：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 1][]

转到正题，开始合并数组

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70][]

这是上面拆分好的数组:\[9\]\[5\]\[2\]\[7\]\[12\]\[4\]\[3\]\[1\]\[11\],合并数组，图片的排序是为了让同学们方便看，和程序执行顺序无关。

合并过程如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 2][]

## 程序实现 ##

### 思路 ###

因为需要将数组替换，又要保留原有位置数据，因此需要一个新的数组来保存排序之后的数据。每次比较，将较小的数据放到新数组的对应位置上，每次排序之后，将新数组的数据按照对应位置将原有数组的数据替换，这样每次比较都是最新的排好序的数组了。

### 代码 ###

public static void main(String[] args) {
            int[] a = {9, 5, 2, 7, 12, 4, 3, 1, 11};
    
            //定义下标
            int right = a.length - 1;
            int left = 0;
            int[] b = new int[a.length];
            mergeSort(a, b, left, right);
            //合并
            for (int i = 0; i < b.length; i++) {
                System.out.print("  " + b[i]);
            }
        }
    
        public static void mergeSort(int[] a, int[] b, int left, int right) {
            if (left == right) {
                //分到最小单位
                return;
            }
            if (left < right) {
                //当未拆分完时继续拆分
                int mid = (left + right) / 2;
                //分组
                mergeSort(a, b, left, mid);
                mergeSort(a, b, mid + 1, right);
    
                //拆分完合并
                //i定义为左边数组起点
                int i = left;
                //i定义为右边数组起点
                int j = mid + 1;
                //新数组下标
                int t = 0;
                //当前两边数组未排序完成时
                while (i <= mid && j <= right) {
                    //定义min接收较小数据
                    int min;
                    if (a[i] < a[j]) {
                        //若当前左边数组i位置上的数据小于右边数组j位置上的数据，说明右边数组j后面位置的数据都大于i对应的数据，
                        // 所以i++向后移动比较下一个左边数组的数据与当前右边数据j的数据。
                        min = a[i];
                        i++;
                    } else {
                        //若左边数组i位置上的数据大于j位置上的数据，则i位置要继续与右边数组剩下的数据进行比较，j++
                        min = a[j];
                        j++;
                    }
                    //将较小数据放到b数组对应位置上，并且下标向后移动一位
                    b[t++] = min;
                }
    
                //若左边数组上还有剩余数据，则放到数组中
                while (i <= mid) {
                    b[t++] = a[i++];
                }
                //若右边数组上还有剩余数据，则放到数组中
                while (j <= right) {
                    b[t++] = a[j++];
                }
    
                //将b数组中的有序数组放到a对应的位置上。
                t = 0;
                while (left <= right) {
                    a[left++] = b[t++];
                }
            }
        }

效果：

![20210205150603943.png][]

合并排序思路不好理解，我是通过excel里面画图理解+自己手敲了好几遍代码加深理解的。希望这篇文章对你们有帮助！喜欢可以点个赞

[Link 1]: https://blog.csdn.net/CAT_cwds/article/details/113401307
[2021020514130557.png]: https://img-blog.csdnimg.cn/2021020514130557.png
[20210205141502785.png]: https://img-blog.csdnimg.cn/20210205141502785.png
[20210205141619390.png]: https://img-blog.csdnimg.cn/20210205141619390.png
[20210205141729256.png]: https://img-blog.csdnimg.cn/20210205141729256.png
[20210205141812509.png]: https://img-blog.csdnimg.cn/20210205141812509.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210205142329921.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210205143331444.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210205145307483.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70
[20210205150603943.png]: https://img-blog.csdnimg.cn/20210205150603943.png