排序-归并排序

原理

  • 假设初始序列含有n个记录，则可以看成是n个有序的子序列;
  • 每个子序列的长度为1，然后两两归并，得到⌈n/2⌉（⌈x⌉表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……;
  • 如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

  • 比如将无序序列 {5,2,9,1,4,7,8,3} 归并排序的流程如下图所示：


递归方式实现

先将无序序列拆分为两个有序的子序列，然后在将 两个有序的子序列 进行归并排序;

<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-3.png" width="500" />

<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-4.png" width="500" />

<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-5.png" width="500" />

<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-6.png" width="500" />

非递归方式实现

<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-7.png" width="500" />
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-merge-8.png" width="500" />

时间复杂度为：O(nlogn)
是最稳定的排序算法
完整代码地址

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容