算法设计与分析(4)——归并排序过程、时间复杂度分析及改进

发布网友 发布时间：2024-10-24 05:05

我来回答

共1个回答

热心网友 时间：2024-10-24 05:38

上一篇文章，我们介绍过第一种基于分治策略的排序算法--快速排序。接下来，我们将讨论另一种基于分治策略的排序算法，归并排序。归并排序被认为是一种时间复杂度最优的算法，我们将按照基本过程、代码、最坏时间复杂度、平均时间复杂度、性能分析和改进这几个方面来展开讲述，为什么归并排序被认为是最优的基于比较的排序算法（理论上）。

一、归并排序过程

归并排序的思想是将待排序序列划分成若干个有序子序列；将两个或两个以上的有序子序列合并为一个有序序列。

我们大体上有两种解决方案：就像上面图片所展示的那样，先分再治。上面的图片已经非常形象地阐明了归并排序的整体过程。

上面这种过程的代码如下所示：

上面这种实现方式就是先不断划分子问题，然后解决最小规模问题，再进行合并。实际上，我们还可以通过第二种方式对这种基本的归并排序算法做一些改进。

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[]数组。如果共做了奇数趟，排序结束，则最多回写一次。

基于这个思路，我们将二路归并排序的代码做一些小小的修改，以满足我们的不回写策略。这和不回写策略也同时消除了递归过程。下面是示例代码。