关于java:深入浅出归并排序一

大家好呀，我是小张，最近整顿材料发现归并排序的思维不仅仅只能够使用到排序中，在于一些其余场景也具备奇效，小张想通过三篇文章来给大家理解这几种场景并把握它，接下来小张先带大家回顾一下归并排序到底是一个什么东东。

说起归并排序，它的思维就是将数据一直切半，而后将切半的数据合并为一个有序过程。

归并

归并归并，那么这个归并到底指的是什么？

假设当初给你一个两局部有序的数组（如下图），要求将两局部有序的数组合并成另一个有序数组。

咱们能够很容易的想到咱们初始化一个和该数组大小统一的辅助数组，设置左中右三个指针，通过左指针和 mid+1 指针以后的数进行比拟，较小的放入辅助数组中指针后移一位。那么循环的终止条件就是 left 指针超过 mid 指针或 mid+ 1 指针超过 right 指针。循环此过程，咱们会发现必定有一半数据会先进入辅助数组，实例的数据，左边的数据将会进入辅助数组，循环终止。

那还有一半数据怎么办？咱们能够通过 left 是否小于等于 mid 或者 mid+ 1 指针是否小于等于 right 来判断数据是否齐全进入辅助数据，如果产生咱们只须要将数据全副增加到辅助数据即可。

代码实现

public void merge(int[] data, int l, int mid, int r) {int[] help = new int[r - l + 1];
        int index1 = l;
        int index2 = mid + 1;

        int i = 0;
        while (index1 <= mid && index2 <= r) {help[i++] = data[index1] <= data[index2] ? data[index1++] : data[index2++];
        }

        // 左边越界
        while (index1 <= mid) {help[i++] = data[index1++];
        }

        // 右边越界
        while (index2 <= r) {help[i++] = data[index2++];
        }

        for (int j = 0; j < help.length; j++) {data[l + j] = help[j];
        }
    }

切分

当初咱们有了一个根底函数merge，那么咱们是否能够将数据切分并将切分后的两个有序数组归并在一起呢？

依照上图，如果咱们能够将数据拆分到不能拆分（只剩一个元素），而后再进行合并，是不是就能够起到排序的作用？

咱们会发现最初一层 merge 之后产生的数组就是有序的数组了，回到第二层就是有序的后果了，上面展现第二层合并的过程。

置信通过图片，大家应该能够明确数据切分而后归并的过程了，其实这里就体现了归并排序的所有思维，接下来将通过代码去实现这个过程。

代码实现

相熟递归的小伙伴会发现这就是一棵典型的递归树，那么咱们就能够通过递归将数据一直的切半，而后再进行合并。

public void sort(int[] data) {sort(data, 0, data.length - 1);
    }

private void sort(int[] data, int left, int right) {
        // base code 当 left=right 代表曾经无奈切分
        if (left == right) {return;}
        int mid = (left + right) / 2;
        sort(data, left, mid);
        sort(data, mid + 1, right);
        merge(data, left, mid, right);
    }

递归函数的退出条件就是，当 left==right 意味着只剩一个元素，就不能往下持续递归了。

写在最初

归并排序的这种分治的思维在平时的解决问题上是经常出现的一种思维，将一个问题的规模一直减小，利用小规模的计算结果一直去推出大规模的后果，这种思维十分值得咱们借鉴。

在下一篇，小张将给大家带来一个可能应用归并排序的场景，将一个工夫复杂度为 O(n^2)算法优化为 O(n*logn)的过程。