请尊重作者的劳动成果,如需转载请注明出处,谢谢！
如果觉得不错,可以关注我或者点赞,这就是你们对我最大的鼓励！
归并排序的思想是:将一个较大的数组(递归的)将他们分成两半分别排序,然后将它们归并起来
归并排序最吸引人的特点是,对于长度为N的数组,排序所需要的时间和NlogN成正比。
缺点也很明显,由于每次都需要将数组复制一份,所以它需要额外的内存,即空间复杂度N。
首先,我们先解决如何将两个数组归并。
代码很简单,如下
归并过程如下图.
首先数组被分为了两个长度分别为 4 和 3的数组
假设这两个数组分别为 array1, array2
首先比较array1[0] 即3 是否比 array2[0] 即5 小 , 若成立，那么 归并到的数组array[0] = 3
此时， array1[1] 即 6 与 array2[0] 即 5 比较 ，明显 5 比 6 小，所以归并到的数组array[1] = 5
然后 array1[1] 即 6 与 array2[1] 即1 比较，明显 1 比 6 小，所以归并到的数组array[2] = 1
如此循环，但是需要考虑一个情况，如果数组array1已经遍历完了呢？此时应当将数组array2剩下的元素放到归并的数组array中。
这种归并称为原地归并。很明显，当两个子数组为有序的情况下，归并的数组也是有序的。可以想象，当两边的数组都只有1个元素时，不用排序，归并的数组也是有序的。
自顶向下的归并排序
很明显，这种排序的方式是从顶部递归二分，然后再归并。这种设计思想为分治思想，分而治之。
示意图如下:
代码实现如下
自底向上的归并排序
换一种思路，其实我们还可以将每个元素归并，获得小数组，再将小数组归并，获取大数组，直至归并成为整个数组。
首先，将每个元素认为是一个大小为1的数组，然后进行归并，数组变成了一堆大小为2的数组，然后再归并。 两两归并，四四归并，八八归并。。。
假设归并如下数组
自底向上归并示意图如下
其实，这种想法很好理解，但是个人认为转换成数学来表达却是难点所在。我们可以通过规律来获取灵感
设归并的子数组的大小用 size 表示
size = 1
merge(array,0,0,1)
merge(array,2,2,3)
merge(array,4,4,5)
merge(array,5,5,6)
merge(array,6,6,7)
size = 2
merge(array,0,1,3)
merge(array,4,5,7)
size = 4
merge(array,0,3,7)
我们发现，size每次变化时, low = 0，high =low + 2 *size - 1，mid = high - size = low + size - 1
当high < array.length 时，low, mid, high的增量都是 2 * size
所以就能得到设计循环的思路啦
代码如下~
自底向上归并排序在最坏的情况下，时间复杂度为NlogN。归并排序的时间复杂度和希尔排序相差为常数级别，即一般情况下没什么区别。
下一篇我们将学习 快速排序。 快速排序因其应用最广泛，实现简单，一般情况下都比其他算法快等特点，导致笔试，考试等都特别喜欢考察。想第一时间获得新文章，可以关注我哦！
网友评论