归并排序算法_归并排序算法的效率类型为平方类型。 ( )

一，归并排序介绍

归并排序是一个典型的基于分治的递归算法。它不断地将原数组分成大小相等的两个子数组(可能相差1)，最终当划分的子数组大小为1时(下面代码第17行left小于right不成立时) ，将划分的有序子数组合并成一个更大的有序数组。为什么是有序子数组？？？

归并排序的递归公式：T(N) = 2T(N/2) + O(N)

从公式中可以看出：将规模为 N 的原问题分解成两个规模 N/2 的两个子问题；并且，合并这两个子问题的代价是 O(N)---[后面的 +O(N) 表示合并的代价]

 

 

二，归并排序算法分析

 归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。

它将数组平均分成两部分: center = (left + right)/2，当数组分得足够小时---数组中只有一个元素时，只有一个元素的数组自然而然地就可以视为是有序的，此时就可以进行合并操作了。因此，上面讲的合并两个有序的子数组，是从 只有一个元素 的两个子数组开始合并的。

合并后的元素个数：从 1-->2-->4-->8......

比如初始数组：[24,13,26,1,2,27,38,15]

①分成了两个大小相等的子数组：[24,13,26,1]    [2,27,38,15]

②再划分成了四个大小相等的子数组：[24,13]   [26,1]    [2,27]    [38,15]

③此时，left < right 还是成立，再分：[24]   [13]   [26]    [1]    [2]     [27]    [38]   [15]

此时，有8个小数组，每个数组都可以视为有序的数组了！！！，每个数组中的left == right，从递归中返回(从19行--20行的代码中返回)，故开始执行合并(第21行)：

merge([24],[13]) 得到 [13,24]

merge([26],[1]) 得到[1,26]

.....

.....

最终得到 有序数组。