归并排序图解：归并排序我来啦
归并排序图解：归并排序我来啦接口2：接口1： 合并的前提是有多个部分，这里是两个部分，左侧和右侧；进入合并的前提是左侧和右侧都已经排序排好了。那么合并只要左侧和右侧中的数据进行比较，谁小排前面，画个图解析下： 不着急写代码，还是先画一下图说明下： 思路逐渐清晰：
#头条创作挑战赛#
初识归并排序归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法采用了分而治之的思想。
基于这个思想，我们就有两个操作，一个排序，一个合并。
排序排序就是将左侧或后侧的数据按照升序或降序排好，一般未说明都指的是升序，在这里合并其实已经包含了比较并交换了也就是排序，其实我不需要在排一遍了，我只需要第一次合并的时候，左侧是1个数，右侧也是1个数，这样不就是有序的嘛，然后合并成两个数，这两个数据就有序了，然后重复这个操作。
合并合并的前提是有多个部分，这里是两个部分，左侧和右侧；进入合并的前提是左侧和右侧都已经排序排好了。那么合并只要左侧和右侧中的数据进行比较，谁小排前面，画个图解析下：
不着急写代码，还是先画一下图说明下：
图画思路
思路逐渐清晰：
接口1：
- 我需要实现拆分。
- 拆分需要调用拆分实现递归。
- 递归最后再调用合并，这样依据递归的逻辑，才能实现拆分到左右各1个元素满足合并的调用条件。
接口2：
- 我需要有个数组可以存放比较的两个数组的值。
- 我需要三个指针，分别指向三个数组的头部。
- 我需要一个循环体，内容是，比较的两个数组的元素，谁小，谁放新数组里，指针后移。
- 循环结束条件是，其中有一个数据空了，具体表现就是指针越界了。
- 越界之后，没有越界的那个数组的剩余数据，需要填入到新数组里。
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
splitSorting(arr 0 arr.length - 1);
}
public static void splitSorting(int[] arr int l int r) {
// 递归终止条件
if (l == r) {
return;
}
int m = (l r) / 2;
// 对于左侧来说，l到中点
splitSorting(arr l m);
// 对于右侧来说，中点 1到右侧
splitSorting(arr m 1 r);
merge(arr l m r);
}
public static void merge(int[] arr int L int M int R) {
// 我需要一个数组存放数据
int[] narr = new int[R - L 1];
// 我需要三个指针，分别指向三个数据的头
int i = 0;
int p1 = L;
int p2 = M 1;
// 我需要一个循环体 结束条件是其中一个越界了 这里写的是循环条件哦，不是结束条件
// p1 p2都在各自的范围内
while (p1 <= M && p2 <= R) {
narr[i ] = arr[p1] <= arr[p2] ? arr[p1 ] : arr[p2 ];
}
// p1 越界，p1添加完了，剩下数据的就是p2
while (p2 <= R) {
narr[i ] = arr[p2 ];
}
// p2 越界，p2添加完了，剩下数据的就是p1
while (p1 <= M) {
narr[i ] = arr[p1 ];
}
// 合并后的narr数据，要放到原来的数组arr里的
for (int j = 0; j < narr.length; j ) {
// L为左侧数据的开始，从L开始放数据
arr[L j] = narr[j];
}
}
呼~~，思路看着挺清晰的，但是写下来还是有不少地方没有说明到的：
- 递归时候千万要注意终止条件，否则会无尽的递归进去，很快就报java.lang.StackOverflowError
- 合并到最后要记得合并后的数据还需要塞回原数组的，否则我们把数据拿出来排了序，之前的数组顺序还是老样子。
刚开始学习归并排序，使用的是递归的写法，明显测试的时候感觉到有点慢，据说还有进阶的写法，后面学到了再更新出来。
