c语言算法 - 分而治之算法 - 归并排序

核心提示：从对归并过程的简略描述中，可以明显地看出归并n个元素所需要的时间为O (n)，c语言算法 - 分而治之算法 - 归并排序(2)，设t (n)为分而治之排序算法（如图1 4 - 6所示）在最坏情况下所需花费的时间，则有以下递推公式：其中c 和d 为常数，长度为1的序列被归并为长度为2的有序序列；长度为2的序列接着被归并为

从对归并过程的简略描述中，可以明显地看出归并n个元素所需要的时间为O (n)。设t (n)为分而治之排序算法（如图1 4 - 6所示）在最坏情况下所需花费的时间，则有以下递推公式：

其中c 和d 为常数。当n / k≈n-n / k 时，t (n)的值最小。因此当k= 2时，也就是说，当两个子集合所包含的元素个数近似相等时，t (n) 最小，即当所划分的子集合大小接近时，分而治之算法通常具有最佳性能。

可以用迭代方法来计算这一递推方式，结果为t(n)= (nl o gn)。虽然这个结果是在n为2的幂时得到的，但对于所有的n，这一结果也是有效的，因为t(n) 是n的非递减函数。t(n) =(nl o gn) 给出了归并排序的最好和最坏情况下的复杂性。由于最好和最坏情况下的复杂性是一样的，因此归并排序的平均复杂性为t (n)= (nl o gn)。

图2 - 6中k= 2的排序方法被称为归并排序（ m e rge sort ），或更精确地说是二路归并排序（two-way merge sort）。下面根据图1 4 - 6中k= 2的情况（归并排序）来编写对n个元素进行排序的C + +函数。一种最简单的方法就是将元素存储在链表中（即作为类c h a i n的成员（程序3 -8））。在这种情况下，通过移到第n/ 2个节点并打断此链，可将E分成两个大致相等的链表。

归并过程应能将两个已排序的链表归并在一起。如果希望把所得到C + +程序与堆排序和插入排序进行性能比较，那么就不能使用链表来实现归并排序，因为后两种排序方法中都没有使用链表。为了能与前面讨论过的排序函数作比较，归并排序函数必须用一个数组a来存储元素集合E，并在a 中返回排序后的元素序列。为此按照下述过程来对图1 4 - 6的伪代码进行细化：当集合E被化分成两个子集合时，可以不必把两个子集合的元素分别复制到A和B中，只需简单地在集合E中保持两个子集合的左右边界即可。接下来对a 中的初始序列进行排序，并将所得到的排序序列归并到一个新数组b中，最后将它们复制到a 中。图1 4 - 6的改进版见图1 4 - 7。

template
M e rgeSort( T a[], int left, int right)
{ / /对a [ l e f t : r i g h t ]中的元素进行排序
if (left < right) {//至少两个元素
int i = (left + right)/2; //中心位置
M e rgeSort(a, left, i);
M e rgeSort(a, i+1, right);
M e rge(a, b, left, i, right); //从a 合并到b
Copy(b, a, left, right); //结果放回a
}
}

图14-7 分而治之排序算法的改进

可以从很多方面来改进图1 4 - 7的性能，例如，可以容易地消除递归。如果仔细地检查图1 4 - 7中的程序，就会发现其中的递归只是简单地重复分割元素序列，直到序列的长度变成1为止。当序列的长度变为1时即可进行归并操作，这个过程可以用n 为2的幂来很好地描述。长度为1的序列被归并为长度为2的有序序列；长度为2的序列接着被归并为长度为4的有序序列；这个过程不断地重复直到归并为长度为n的序列。图1 4 - 8给出n= 8时的归并（和复制）过程，方括号表示一个已排序序列的首和尾。

初始序列[8] [4] [5] [6] [2] [1] [7] [3]

归并到b [4 8] [5 6] [1 2] [3 7]

复制到a [4 8] [5 6] [1 2] [3 7]

归并到b [4 5 6 8] [1 2 3 7]

复制到a [4 5 6 8] [1 2 3 7]

归并到b [1 2 3 4 5 6 7 8]

复制到a [1 2 3 4 5 6 7 8]

图14-8归并排序的例子