归并排序

归并排序是用到了分治的思想,分治的思想是将一个大问题拆分成很多的小问题,然后再将已经处理完成的小问题合并成整个的大问题。在这个过程中,大问题就得到了解决。在大数据方面的 Map-Reduce 就是这样的分治的思想。

归并排序首先将数组等分,然后排序等分后的数组,最后再将排好序的两个数组合并成一个排好序的数组。归并排序的时间复杂度是O(n log n)

为了能够更好的理解归并排序,我们来看下面的数组:

依然是上次我们用到的没有排序的数组,上面总共有八个数字,等分后就会变成每组四个数字。这样的等分一直持续到只剩下一个数字的情况。

由于还没有将数组等分到只有一个元素的情况,所以我们继续等分。

此时,每个分组中只有两个数字,还是可以继续等分。

在这个时候,等分结束。因为所有的分组都只能分到这种程度,没有数组还能继续等分了。

然后我们将数组进行俩俩合并,首先我们需要比较两个数组中的每一个数据,然后将这些数据放入一个新的数组中,新数组就是有序的。这里比较的过程就是 14 和 33 是升序的,不需改变。27 和 10 是降序的,需要先放入10,再放入27. 35 和19也是降序的,需要先放入19, 再放入27. 最后,42 和 44 是升序的,不需改变。

再下一次将前两个合并到一个数组中,后面两个合并到一个数组中。过程是:前两个数组合并,先判断14 和 10,发现 14 要 大于10,所以在新生成的数组中将 10 写在第一个位置上。然后比较14 和 27 发现14小,将 14 写在新生成的数组的第二个位置。在比较33 和 27,发现27 小,将27写在新生成的数组中。由于第二个数组写入完成,所以将第一个数组的剩余部分写入新生成的数组。第三组和第四组合并过程也是类似:19 vs. 42 => 19, 35 vs. 42 => 35, 一个结束另一个写入剩余的部分=>42, 44

最后,经过最终的merge操作,生成的数组就是下面的这个模样:

前面的算法都没有写代码,是因为前面的代码都是两个循环就解决问题的,读者可以自己解决,归并算法非常重要,所以我们需要为它写一下代码。python语言实现。

python 语言实现(没有上代码,是图片,自己敲几遍!!):

若是各位有什么想要了解的内容同样可以与我讨论,感谢大家的支持!!

喜欢可以关注公众号哦

子曰:“赐也,女以予为多学而识之者与?”对曰:“然。非与?”曰:“非也,予一以贯之。”

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181005G0DIIG00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券