• 如需转载请标明出处：https://blog.****.net/zhuzi9
• QQ技术交流群：594200841

前言

概念介绍

• 归并排序算法是建立再归并操作上的一种有效的排序算法。
• 该算法是采用分治法的一个非常典型的应用
• 归并排序的两种实现方式

1. 自上而下的递归
2. 自下而上的迭代

原理讲解

以[11 41 45 42 36 27 40 4]这个序列为例说明归并排序算法的实现原理

1. 未开始遍历时，此时效果如下图
   
2. 我们将这个序列的8个元素人为的看成序列[11 41 45 42 36 27 40 4]的8个子序列[11],[41],[45],[42],[36],[27],[40],[4]，此时效果如下图
   
3. 将上述8个子序列两两归并（值小的元素在前，值大的元素在后）得到4个新的子序列[11 41],[42 45],[27 36],[4 40]，此时效果如下图
4. 将上述4个子序列两两归并（值小的元素在前，值大的元素在后）得到2个新的子序列[11 41 42 45],[4 27 36 40]，此时效果如下图
   
5. 将上述2个子序列两两归并（值小的元素在前，值大的元素在后）得到1个新的序列[11 41 42 45],[4 27 36 40]，此时效果如下图
   
6. 至此，整个归并排序流程讲解完毕。整体效果下图
   

时间复杂度

• 从归并算法实现过程中可以看出每次合并操作的时间复杂度是O(N)，而二叉树的深度是log2^N
• 故归并算法总的时间复杂度是O(N*log2^N)

空间复杂度

• 临时申请的数组的数据占用的空间n， 递归时压入栈的数据占用的空间logn；
• 故归并算法总的空间复杂度为: O(n)

算法优缺点

• 优点：效率高，达到了基于比较排序的效率巅峰；算法稳定
• 缺点：空间复杂度较高

效果展示

源码下载

• 链接如下https://download.****.net/download/zhuzi9/12506345

更多算法学习请关注我的公众号

• 如需转载请标明出处：https://blog.****.net/zhuzi9
• QQ技术交流群：594200841