用一次手工合并看懂归并排序为什么稳定

举报
yd_220846312 发表于 2026/11/17 14:23:22 2026/11/17
【摘要】 用数组 [3, 1, 3, 2] 把归并排序的分治和合并走一遍,说明相等元素为什么不会被打乱,以及时间代价和额外空间各自从哪一步来。

归并排序把数组不断对半切开,切到只剩一个元素,再两两合并。难点不在切开,而在合并时怎么保持原有的先后顺序。

拿 [3a, 1, 3b, 2] 做例子。两个 3 用下标区分,只是为了观察稳定性,数值仍然都是 3。

第一轮切分:左半 [3a, 1],右半 [3b, 2]。再切开就是单个元素:3a 与 1,3b 与 2。

合并 [3a] 和 [1]:1 更小,先放 1,再放 3a,得到 [1, 3a]。合并 [3b] 和 [2]:2 更小,得到 [2, 3b]。

关键的一次合并是 [1, 3a] 和 [2, 3b]。比较 1 和 2,取出 1;比较 3a 和 2,取出 2。剩下 3a 和 3b,两者相等。稳定排序的约定是:相等时先取左半边那个,也就是更早出现的 3a。结果是 [1, 2, 3a, 3b]。

如果相等时改成优先取右边,3b 会跑到 3a 前面,排序就不稳定了。所以说归并稳定,指的就是合并时相等元素保留左段。

代价也从这一步看。每一层合并都要把当前这一层的全部元素各看一遍,一层是 O(n)。数组每次对半,大约 log n 层,所以整体是 O(n log n)。额外空间来自合并用的辅助数组。不能在原数组里左右对撞着写,否则还没读到的值会被覆盖。

写代码时还要单独处理奇数长度:左段可能比右段多一个。两侧指针比完之后,把没取完的那一侧整段拷到结果里,合并才算做完。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0)

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。