思绪
有数组[2, 1, -3, -15, 25, 16, 0, 8]如下：
现对该数组举行排序，使用归并排序算法。
先来讲授一下归并排序的思绪，大概分为如下几个步调：
- 先将原数组先辈行拆分，拆分成多少个富足小的子数组；
- 将子数组举行排序；
- 将子数组逐一举行归并，直到全部子数组被归并。
讲授
OK，思绪相识了，下面就用图示来演示一下各个步调是怎么做的。
1. 先将原数组先辈行拆分，拆分成多少个富足小的子数组：
我们先把上面的数组举行第一次拆分：
拆分成了两部分，分别为[2, 1, -3, -15]和[25, 16, 0, 8]
如许的拆分不够小，我们继续举行拆分：
如许就又把两个子数组分别拆分成了更小的两个子数组[2, 1]、[-3, -15]、[25, 16]、[0, 8]。
好了，如许的拆分富足小了，举行下一步。2. 将子数组举行排序：
排序后的四个子数组为：
子数组排序后，就该举行末了一步了。
3. 将子数组逐一举行归并，直到全部子数组被归并：
先将第一个子数组和第二个子数组举行归并，归并的步调着实也很简朴，就是将两个子数组的元素从左到右依次举行比力，按序次举行存放即可。
这时间需要创建一个空数组，对结果集举行一个存放。首先对比1和-15，1比-15要大，以是先把-15放到结果数组中：
然后对比1和-3,1依然是大于-3，以是把-3放到结果数组中：
这时间第二个子数组已经被搬空了，那么直接把第一个子数组的数据依次放入结果数组即可：
如许前面两个子数组就完成了归并操纵。那么背面两个子数组也是同样的归并方式，归并结果如下：
如许就归并成了两个子数组，然后再对这两个子数组举行进一步的归并操纵，操纵依然跟上面是一样的，一个一个对比，终极就归并成了如下结果：
如许就完成了一个简朴的归并排序。
但一般生产中大概需要排序的数据会比力大，那么拆分的时间大概拆分到15个左右元素的时间，就不再举行拆分了，而是使用插入排序的方式对子数组举行排序，然后再对排好序的子数组举行归并。实现
下面来用代码实现一下归并排序： |
