归并排序算法解析

对于基本的排序算法,前面介绍了冒泡,选择,插入和希尔(增强版本的插入), 还有快速排序,现在还剩下最后一种基本的排序算法,那就是归并排序。归并排序像快速排序一样采用递归算法对列表进行分而治之,每次平均一分为二,分到只有一个元素为止。如果列表为空或只有一个元素时,那么从定义上来说它就是有序的; 当然归并排序的拆分最终不会有空列表的情况。拆分成一个个元素后再往回归并,归并是指将两个较小的有序列表归并为一个有序列表的过程。比如说两个单元素列表归并为两个元素的有序列表,两个双元素的列表归并为四个元素的有充列表,不断往上进行,最后形成一个有序的完整列表。

从维基百科的词条 Merge sort 找到下图,很深刻的描绘了归并排序的完整过程,红色箭头拆分,绿色箭头归并

如果根据以上的原理开始自己来写整个,用递归来拆分比较简单,对两个子列表归并时也有个排序过程,这其中会有个什么排序方式呢?

该代码执行的效果与上图略有不同,因为 Python 的 // 操作是向下取整除法,如果要达成与图中一样的拆分效果的话,取 middle 索引时就必须用

另外把左半或右半部分剩余元素除加到原列表时的代码也可以写成如下

现在来看一下归并排序的时间复杂度,对半拆分时是 O(log n),归并是拆分出来的每个列表要遍历一次,所以归并排序整体的时间复杂度是 O(n log n)。空间方面我们在切片时使用了额外的空间,如果每次用索引范围来标记拆分与合并可以节省不必要的空间,即 In-Place。

参考一个更能节省空间的 Python 归并排序写法,来自 GeeksforGeeks 的 Merge Sort

采用 append, pop 操作免去了记忆三个索引的麻烦,只时 pop(0) 时会引起其后所有元素位置的调整,Python 的 List 的  pop(0) 是 O(n) 操作,如果是一个链表则是 O(1)

与插入,希尔排序的速度对比

比较代码如下:

结果

排序耗时(秒) 有序列表(1K) 有序列表(10K) 有序列表(100K) 无序列表(1K) 无序列表(10K) 无序列表(100K)
插入排序 0.000178472 0.002385171 0.023859703 0.05322551 5.83567684 590.22879396
希尔排序 0.00668545 0.067583564 1.062383998 0.00893686 0.260694217 16.79080933
归并排序 0.002503669 0.03103195 0.392614932 0.003419672 0.048290216 0.737126917
快速排序 0.00121311 0.014746089 0.232392676 0.001602581 0.019787454 0.331404756

归并排序在整体表现上还是很不错,它同快速排序都是一样的 O(n log n) 时间复杂度,所以还是有一定资格拿它与快速排序相比较的。从某种意义上讲快速排序是对归并排序的改进

  1. 归并排序是每次对半拆分,快速排序选定基准值进行拆分
  2. 归并排序拆分时不用与基准值的比较,拆分效率高于快速排序
  3. 它们都是要拆分到只剩下单个元素的列表
  4. 归并排序在归并时合并子列表麻烦些,快速排序合并子列表直接串起来 -- 归并排序效率差在这里
  5. 归并排序归并是一次遍历,快速排序在拆分时要一次遍历,所以它们的复杂度都是 O(n log n)

虽然它先要傻傻的把整个列表拆成全是单元素的列表,但归并是处理的都是有序列表,这可省了不少的时间。所以归并排序不在于怎么拆分,关键在于归并的过程上的高效,所以才叫做归并排序。由于它采用折半拆分,也就不能容易造成调用栈溢出的情况,因为 32 的栈深度可以处理 232 = 4294967296 个元素,Python 默认的栈深度 sys.getrecursionlimit() 是 1000。

类别: Algorithm. 标签: , . 阅读(40). 订阅评论. TrackBack.
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x