算法设计与分析(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[]数组。如果共做了奇数趟，排序结束，则最多回写一次。
基于这个思路，我们将二路归并排序的代码做一些小小的修改，以满足我们的不回写策略。这和不回写策略也同时消除了递归过程。下面是示例代码。
