算法设计与分析(4)——归并排序过程、时间复杂度分析及改进
发布网友
发布时间:2024-10-24 05:05
我来回答
共1个回答
热心网友
时间:2024-10-24 05:34
上一篇文章,我们介绍过第一种基于分治策略的排序算法--快速排序。接下来,我们将讨论另一种基于分治策略的排序算法,归并排序。归并排序被认为是一种时间复杂度最优的算法,我们将按照基本过程、代码、最坏时间复杂度、平均时间复杂度、性能分析和改进这几个方面来展开讲述,为什么归并排序被认为是最优的基于比较的排序算法(理论上)。
一、归并排序过程
归并排序的思想是将待排序序列划分成若干个有序子序列;将两个或两个以上的有序子序列合并为一个有序序列。
我们大体上有两种解决方案:就像上面图片所展示的那样,先分再治。上面的图片已经非常形象地阐明了归并排序的整体过程。
上面这种过程的代码如下所示:
上面这种实现方式就是先不断划分子问题,然后解决最小规模问题,再进行合并。实际上,我们还可以通过第二种方式对这种基本的归并排序算法做一些改进。
2.二路归并排序
其实我们还有另外一种解决方案:将n个待排序的数据直接划分成n个规模为1的子序列。然后进行二路归并排序。
二路归并排序直接将n个待排序的数据元素看成n个有序子序列,依次合并两个相邻有序子序列,直到只剩下一个有序子序列为止。
示例代码如下所示:
很容易可以看到区别,我们将递归过程改为非递归过程。
二、归并排序的时间复杂度分析
归并排序特点:最坏情况是最后一次比较两个有序子序列各自剩最后一个数据元素。例如[公式] 这个两个子序列合并一共需要比较n-1次,是最坏情况。同理我们也很容易分析出最好情况,就是(1,2,3,4)和(5,6,7,8)这两个序列,只需要比较n/2=8/2=4次即可。
我们基于分治法时间复杂度公式进行分析
[公式]
则我们有分析公式如下
则我们可以大胆得出结论,归并排序最坏情况时间复杂度为[公式] 。
2.最好情况时间复杂度
最好情况时间复杂度也是[公式] 。
最好情况与最坏情况的时间复杂度都是nlogn量级的,那么我们也很容易得出结论(类比与高等数学的夹逼准则)归并排序的平均时间复杂度也为nlogn量级。
三、归并排序改进措施
详细过程:
思路:奇数趟从E[]写到B[]数组,偶数趟从B[]写到E[]数组。如果共做了奇数趟,排序结束,则最多回写一次。
基于这个思路,我们将二路归并排序的代码做一些小小的修改,以满足我们的不回写策略。这和不回写策略也同时消除了递归过程。下面是示例代码。