归并排序
归并排序把一个难题变成许多简单问题:两个有序列表很容易合并成一个。把列表对半拆分,直到每一块都只有一个值,再把这些块合并回去。它是经典的分治算法,无论输入如何,时间都是 n log n。
基本思路
合并是简单的部分。给定两个各自有序的列表,比较它们的第一个值,取较小的那个。再比较新的第一个值,再取较小的。一个列表取完后,把另一个剩下的部分接在后面。每一步取一个值,所以合并总长度为 m 的两个列表最多需要 m − 1 次比较。归并排序就利用这一点排序:把列表对半拆分,用归并排序排好每一半,再合并两半。
示例
以 5, 1, 4, 2, 8 为例。拆成 5, 1 和 4, 2, 8。前一半拆成 5 和 1,合并成 1, 5。后一半拆成 4 和 2, 8;2, 8 由 2 和 8 合并而来,再与 4 合并成 2, 4, 8。最后合并 1, 5 和 2, 4, 8:依次取 1、2、4、5,剩下 8。共 8 次比较、12 次写回和 4 次合并。
为什么是 n log n
每次拆分都让块减半,所以大约 log₂ n 层后每一块都只有一个值。往回合并时,每层合并都处理每个值一次,即每层 n 次写回和少于 n 次比较。总计约 n log₂ n。40 个值时,排序进行 216 次写回、最多 177 次比较;同样的列表,冒泡排序可能需要 780 次比较。输入顺序的影响也比那些排序小得多:40 个值时,有序列表需要 100 次比较,倒序列表 116 次,随机列表约 160 次。
缓冲区与稳定性
要合并列表中相邻的两半,常用方法是把它们复制到缓冲区,再按顺序写回。本应用把缓冲区显示为第二行柱子。它需要与列表同样多的额外内存,这是归并排序的主要代价。作为回报,排序是稳定的:两个首个值相等时,左半部分的先放,所以相等的值保持原来的顺序。按多个字段依次排序记录时,稳定性很重要。
历史与应用
John von Neumann 于 1945 年描述了归并排序,使它成为最早为存储程序计算机编写的算法之一。由于它以长段连续的方式读写数据,它曾是在磁带上排序数据的标准方法,现在仍用于内存装不下的大文件。Python 以及 Java(用于对象)使用的 Timsort 就是一种归并排序:它先找出已经有序的片段,并对短片段使用插入排序。
动手探索
打开应用,按“单步”。列表中带阴影的部分正在被拆分或合并,虚线标出中点。合并开始时,两半都落入缓冲区那一行;比较两个首个值,较小的移回上方。留意计数器:同样长度的列表写回次数都相同;比较次数在有序或倒序列表时最少,随机列表时最多,但绝不会超过约 n log₂ n。
常见问题
归并排序的时间复杂度是多少?
最好、平均和最坏情况下都是 O(n log n)。常见版本需要 O(n) 的额外内存作为缓冲区。
归并排序和快速排序有什么区别?
两者都把列表分开再排序各部分。归并排序不看值,直接从中间拆分,工作在合并时完成;快速排序的工作在拆分时完成,即围绕基准值移动元素,不需要合并。快速排序是原地排序,实际中往往更快,但遇到不利的输入可能退化到 n²,而且不稳定。归并排序始终是 n log n,而且稳定。
什么是自底向上的归并排序?
一种不用递归的版本:先把相邻的单个值合并成两个一组,再把两个一组合并成四个一组,依此类推,每轮长度翻倍。它的工作量与这里展示的自顶向下版本相同。
归并排序稳定吗?
稳定,只要值相等时先取左半部分的值,本应用就是这样做的。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试归并排序