归并排序

面试官： 聊聊归并排序

归并排序是建立在归并操作的一种高效的排序方法，该方法采用了分治的思想，比较适用于处理较大规模的数据，但比较耗内存，今天我们聊聊归并排序

排序思想

一天，小一尘和慧能坐在石头上，眺望着远方

师傅，我听山下的柳公子说他们导员要管理五六百的学生，这么多学生怎么管的过来呀

一尘

慧能

这么多人一块管理肯定是不行的，需要分开来管理

哦？分开来管理

一尘

慧能

你看每个班是不是都会选一个班长，班长把班里的学生管理好，导员把班长管理好，这不就全部学生都管理好了

慧能

这种方法其实就是分而治之，所谓分而治之就是把一个复杂庞大的问题分解成一个个小的问题去解决

分而治之： 分开来去治理

慧能

这种思想在编程中非常重要，归并排序就是一个典型的应用

哦，什么是归并排序？

一尘

慧能

所谓归并排序，就是将待排序的数分成两半后排好序，然后再将两个排好序的序列合并成一个有序序列

归并即合并之意

慧能随手画了一张图解释了一下

治：治理，这里就是将数组排序

哦，怎么去治（排序子数组），又怎么去合（合并两个有序子数组）？

一尘

慧能

至于治，你只需不断地分，一直分到只有一个元素的时候，这个时候就不治而治了（一个元素认为它有序）

慧能

对于合并，其实非常简单，我只要不断地取出两个有序数组中比较小的那一个放在一个辅助数组中（通过比较），直到把两个有序数组中的元素取完

哦，我懂了，原来是这样

一尘

代码

慧能

懂了就写一写代码吧

哦！

一尘

一尘已经了解了师傅的固定套路了

既然是不断地分，那用递归就非常简单了，什么时候终止递归呢？递归到只有一个元素的时候。一尘随手写下了如下代码

关于center = (left+right)/2的改进可看：二分查找（代码讲解块有）

很快，一尘写下了merge函数的代码

先把 arr 数组子数组合并到辅助数组，然后再把有序的辅助数组copy到 arr 数组中

一尘

一尘解释道

时间复杂度

慧能

时间复杂度分析必不可少

一尘想到：这个有点烧脑啊，元素个数为 n，运行时间是多少啊？递归,递归，再递归...

慧能

不用想递归了

师傅一下看出了一尘的心思

那怎么算呢？

一尘

慧能

其实并不复杂

假设处理的数据规模大小为 N

运行时间设为：T(N)

① 当把 N 分为两半时，那么处理大小为 N/2 子数组花费时间为：T(N/2)

② 合并花费时间与数据规模成正比:N

所以处理规模大小为N的数据所需要花费两个大小为 N/2 的子数组加上合并花费的时间

即：T(N) = 2T(N/2) + N

对于 N = 1，T(1) = 1

慧能

那么现在只需要求出T(N)即可

假设N是2的幂

慧能

对于N不是2的幂的情况，答案几乎一样

哦，复杂度原来这样算

一尘

关于时间复杂度可以看：

算法分析神器—时间复杂度

稳定性

慧能

最后说以下稳定性吧

是稳定的，因为在合并的时候，如果相等，选择前面的元素到辅助数组

一尘

关于稳定性可以看：冒泡排序（文末有）

此时太阳已经下山，一尘和师傅走在回家的路上，在路上，一尘脑子又想了一下归并排序的全过程（点击视频观看）