比较
写回
合并

  • 正在合并的部分
  • 比较中
  • 已写回
  • 已合并部分

更多关于归并排序

归并排序

归并排序是一种分治算法。它把列表对半拆分,用同样的方法排序每一半,再反复取较小的首个值,把排好的两半合并起来。观看两半被移入缓冲区那一行、再按顺序写回,可任意调速或逐步查看,并统计比较、写回和合并次数。 按“播放”观看排序过程,或用“单步”和“后退”逐步查看。拖动步骤滑块可跳到任意位置。卡片统计比较次数、写回次数和合并次数。可选择柱子数量、初始顺序,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择柱子数量和初始顺序:随机、基本有序、倒序或少量不同值。也可以输入自己的数字。
  2. 按“播放”,或用“单步”和“后退”逐步查看。拖动步骤滑块可跳到排序的任意位置。
  3. 观察每次合并:排好的两半下移到缓冲区,较小的首个值逐个移回上方。

归并排序的原理

单个值本身就是有序的。更长的列表则拆成两半,分别用归并排序排好。然后合并:查看每一半的首个值,把较小的移入结果,重复直到两半都为空。因为两半都已有序,结果也是有序的。

始终是 n log n

一再对半拆分大约得到 log₂ n 层,每层合并都把每个值写回一次,所以排序大约进行 n log₂ n 次写回,比较次数最多也是这么多。与冒泡、选择和插入排序不同,它不会随 n² 增长,列表顺序的影响也小得多。代价是一个和列表一样长的缓冲区。归并排序还是稳定的,因此 Python 和 Java 的排序都以它为基础。

常见问题

归并排序是怎么工作的?

它把列表对半拆分,用归并排序排好每一半,再反复取两半首个值中较小的那个,把两半合并起来。只有一个值的列表本身就有序,所以拆到这里就停止。

归并排序要进行多少次比较?

对 n 个值,最多约 n log₂ n − n + 1 次,最少约为 n log₂ n 的一半。40 个值时最多 177 次。对给定的 n,写回列表的次数总是相同:每层合并中每个值写回一次。

归并排序为什么需要额外内存?

原地合并两半很难做得快,所以常见的归并排序把两半复制到缓冲区,再按顺序写回。缓冲区和列表一样长,这是它相比快速排序和堆排序的主要缺点。

归并排序稳定吗?

稳定。两个首个值相等时,左半部分的先放,所以相等的值保持原来的顺序。

我的数字会被发送到别处吗?

不会。排序在你的浏览器中运行,上次的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器