看图轻松理解数据结构与算法系列(合并排序)

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


合并排序

合并排序也叫归并排序,它的主要思想是分治法,把待排序序列分为若干有序子序列,然后将两个或两个以上的有序子序列进行合并,得到一个新的完整的有序序列。所以首先得先对子序列进行排序,得到有序子序列,然后再使序列段之间有序。

排序要点

既然是分治法,那么就涉及到分和治。分,即递归地将序列分成小序列再求解;治,即递归地将分成的小序列合并到一起。

  1. 设序列长度为L,将序列分为两个长度为(L/2)的子序列。
  2. 继续递归地对两个子序列分割,直至不能再继续分割,此时每个子序列只有一个元素。
  3. 对分割后的子序列进行递归地合并,按一定顺序组合成有序子序列,有序子序列之间继续合并。
  4. 最终合并成一个完整的长度为L的有序序列。

排序过程

假设我们有如下8个元素,分别为84,25,59,71,62,16,34,45,现在进行合并排序。

image

先将0到3分为子序列,4到7分为子序列,

image

对于0到3子序列,继续分为0到1的子序列,2到3的子序列,

image

对于0到1子序列,继续分为0子序列和1子序列,然后对这两个子序列进行合并,两个子序列都只有一个元素,一个元素的序列可以看成是有序序列,我们把它们合并成有序序列,25小,先提出来,

image

然后是84,

image

排好序的序列放回原来序列中,于是完成0和1子序列的合并操作,01变成有序子序列。接着处理2子序列和3子序列,

image

59比较小,先提出来,

image

然后是71,

image

排好序的序列放回原来序列中,于是完成2和3子序列的合并操作,23变成有序子序列。

image

接下去开始合并01有序子序列和23有序子序列,01序列中最小的元素25小于23序列中最小的元素59,于是25先提出来,

image

01序列剩余元素中最小元素84大于23序列中最小的元素59,于是59提出来,

image

84与71比较,提出71,

image

最后提出84,

image

于是完成0到3的合并,0到3变为有序序列,放回原序列中。接下去处理4到7的子序列,

image

继续分为4到5的子序列,6到7的子序列,

image

对于45子序列,继续分为4子序列和5子序列,然后对这两个子序列进行合并,两个子序列都只有一个元素,一个元素的序列可以看成是有序序列,我们把它们合并成有序序列,16小,先提出来,

image

然后是62,

image

排好序的序列放回原来序列中,于是完成4和5子序列的合并操作,45变成有序子序列。接着处理6子序列和7子序列,

image

34较小,先提出来,

image

然后是45,

image

排好序的序列放回原来序列中,于是完成6和7子序列的合并操作,67变成有序子序列。

image

接下去开始合并45有序子序列和67有序子序列,45序列中最小的元素16小于67序列中最小的元素34,于是16先提出来,

image

45序列中剩余元素中最小元素62大于67序列中最小的元素34,于是34提出来,

image

62与45比较,提出45,

image

最后提出62,

image

于是完成4到7的合并,4到7变为有序序列,放回原序列中。现在我们已经完成了0到3的有序序列和4到7的有序序列,接下去开始合并03序列和47序列,

image

03序列最小元素25与47序列最小元素16比较,选出小的16,

image

继续比较两个序列最小的元素,25与34比较,选出25,

image

接着59与34比较,选出34,

image

59与45比较,选出45,

image

59与62比较,选出59,

image

71与62比较,选出62,

image

然后剩下的71和84不用比较了,因为47序列已经没有元素了,直接按照原来顺序提出来即可,

image

最终完成排序。

image

赞(1) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 看图轻松理解数据结构与算法系列(合并排序)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏