雅乐网

计算机技术、学习成长

计算机 » 算法 » 归并排序

归并排序

归并排序是分治思想的典型应用。它的基本步骤有3步:

1. 划分。将要排序的数组分为两部分。

2. 递归求解。分别递归使用归并排序将两部分排序。

3. 合并。将两个有序的序列合并为一个有序的序列。

将序列分为两部分用时O(1),而对子序列进行递归排序耗时2 * T(n/2),对排好的两个序列合并用时O(n)。

由于每次减为n/2 。算法的总体复杂度为O(nlogn)

61e439e5g79e8403413d0&690

主代码mergesort

代码的主体部分如下:

思想是,排序前半部分,排序后半部分,将两部分归并为一个部分。

 归并两个有序序列

只需每次比较两个序列的第一个,取出较小者,再比较两个序列的第一个……

左半部分[low, mid) 右半部份[mid, high)

代码如下

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/merge_sort.html

上一篇:

下一篇:

我要评论

验证码*: 9 + 3 =