算法-合并排序

思想

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

画图分析

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

先拆分数据：

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

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

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

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

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

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

转到正题，开始合并数组

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

合并过程如图：

程序实现

思路

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

代码

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++];
            }
        }
    }

效果：

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