Python中怎么实现归并排序

Python中怎么实现归并排序，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。

归并排序

归并排序是分治策略在排序中的应用

归并排序本质上是递归算法，思路是将数据表持续分裂成两半，对两半部分分别进行归并排序

• 递归的基本结束条件：数据表仅剩一个数据项（此时整个数据表都已经排序好了）

• 缩小规模：将数据表分裂成相等的两半，这样规模就减半了，并朝着基本结束条件挺进

• 调用自身：将两半部分分别调用自身进行归并排序，然后分别将排好序的两半部分进行合并，得到排序好的数据表

归并排序的具体步骤（两个部分）：

1. 先将数据表不停的二分，分到最后只有一个数据项，不能再分了

2. 开始进行合并，合并的时候进行排序

 

1. 利用递归调用不停的拆分数据表

2. 递归结束后，左右两部分数据都已经排序好了

3. 针对左右两部分进行逐个比对，小的提取出来放到结果列表中

   拉链式交错将左右部分从小到达合并到结果列表中

4. 最后，如果有一方清空了，则另一部分剩下的都是大数据项，且有序。直接接到结果列表后面

拆分的方法：数组切片

合并的方法：左右两部分数组逐个元素比对（循环条件，左右部分都还有元素）

算法分析

归并排序主要有两个过程：分裂和归并

• 分裂：O(logn) 参考二分查找

• 归并：O(n) 所有元素都会被比对放置一次

归并排序的时间复杂度：O(nlogn)

从时间复杂度来看，归并排序的效率很好。但是要注意，在空间性能上，归并排序需要额外一倍的存储空间用于合并过程，这是一个面都大数据时的缺点

看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注亿速云行业资讯频道，感谢您对亿速云的支持。