合并排序算法

有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次或多次地递归调用起自身来解决相关的子问题 。这些算法通常采用分治策略：将原有问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治模式在每一层递归上都有三个步骤：

分治（Divide）：将原问题分解成一系列子问题；

解决（Conquer）：递归地解各子问题。若子问题足够小，则直接求解；

合并（Combine）：将子问题的解合并成原问题的解

合并排序（Mergesort）算法完全依照了上述模式，直观地操作如下：

分解：将n个元素分成各含n/2个元素的子序列；

解决：用合并排序法对两个字序列递归地排序；

合并：合并两个已排序的子序列。

在对子序列排序时，其长度为1时递归结束。单个元素被视为已排序的。

合并排序的关键步骤在于合并两个已排序的子序列。为此，引入一个辅助过程MERGE(A, p, q, r)，其中A是个数组，p、q、r是下标，满足p <= q < r。该过程假设子数组A[p .. q]和A[q+1 .. r]都已排好序，并将它们合并成一个已排好序的子数组代替当前子数组A[p..r]。 

合并排序的算法如下：

MERGE-SORT(A, p,  r)

    //如果只有一个元素，即p = r，则递归结束，否则继续分治   

    if p < r

        then q = (p + r) / 2 向下取整

                //以q为界，将数组分解成两个子数组，对子数组进行排序，然后再将已排序的子数组合并

                MERGE-SORT(A, p, q)

                MERGE-SORT(A, q + 1, r)

                MERGE(A, p, q, r)

 

辅助过程MERGE的伪代码如下：

MERGE(A, p, q, r)   

    //子序列A[p .. q]的长度

    n1 = q - p + 1

    //子序列A[q+1 .. r]的长度

    n2 = r -q

    //创建临时数组L和R

    create arrays L[1 .. n1+1] and R[1 .. n2+1]

    //将子序列A[p .. q] 和 A[q+1 .. r]分别备份到数组L和R中。

    for i = 1 to n1

        L[i] = A[p + i - 1]

    for j = 1 to n2

        R[j] = A[q + j]

    //放置哨兵

    L[n1 + 1] = ∞

    R[n2 + 1] = ∞

    //合并已排序子数组，使得A[p .. r]有序，参考下面的示意图

    i = 1

    j = 1

    for k = p to r

        if L[i] <= R[j]

            then A[k] = L[i]  

                    i++

            else A[k] = R[j]

                    j++

 

合并已排序子数组的示意图(展示了当k = p + 4时，各个下标的取值。此时，应该挑选L[i]覆盖A[k]，然后k和i向后移动)：

说明：

1、数组A中绿色部分，表示子数组A[p .. r]排序后的最终值，灰色部分表示将被覆盖的值。数组L和R中，绿色部分表示已被复制会A中的元素，白色部分表示有待被复制回A的值。

2、在合并过程中，如果不设置哨兵元素的话，在对L和R中的元素进行比较时，需要判断下标是否越界（或则比较是否已到数组末尾）。

如果加入哨兵元素，则可简化判断。比如，示意图中数组R将先被合并完成，j指向∞，此后L中所有的元素（除了哨兵），都比R当前的元素（哨兵）小，直接将L中的元素覆盖A中对应的元素即可。

 

总结：合并算法采用分治策略，时间复杂度为o(nlgn)。

 

今天抽点时间，写了一个归并排序的模板，适用于内置类型和用户自定义类型，但要求用户自定义类型重载“<”和“>”操作以及输出操作符。代码如下：

[cpp]  view plain copy

1. #include <iostream>  
2. using namespace std;  
3.   
4. template<typename T>  
5. bool ElemAsc(const T &left, const T &right)  
6. {  
7.     return left < right;  
8. }  
9.   
10. template<typename T>  
11. bool ElemDesc(const T &left, const T &right)  
12. {  
13.     return right < left;  
14. }  
15.   
16. template<typename T, class CompareFunc>  
17. void Merge(T *pArray, int iLow, int iMid, int iHigh, CompareFunc func)  
18. {  
19.     //左边子数组的长度  
20.     int iLeftLen = iMid - iLow + 1;  
21.     T *pLeft = new T[iLeftLen];  
22.     //备份  
23.     memcpy(pLeft, pArray + iLow, iLeftLen * sizeof(T));  
24.   
25.     //右边子数组的长度  
26.     int iRightLen = iHigh - iMid;  
27.     T *pRight = new T[iRightLen];  
28.     //备份  
29.     memcpy(pRight, pArray + iMid + 1, iRightLen * sizeof(T));  
30.   
31.     //归并（这里没法放置哨兵，因为无法知道T类型的极值，所以这里增加了对子数组是否越界的处理）  
32.     int iLeftIndex = 0, iRightIndex = 0;  
33.     for(int iFinalIndex = iLow; iFinalIndex <= iHigh; iFinalIndex++)  
34.     {  
35.         //特殊情况1：右边子数组已经合并完成  
36.         if(iRightIndex == iRightLen)  
37.         {  
38.             pArray[iFinalIndex] = pLeft[iLeftIndex++];  
39.             continue;  
40.         }  
41.   
42.         //特殊情况2：左边子数组合并完成  
43.         if(iLeftIndex == iLeftLen)  
44.         {  
45.             pArray[iFinalIndex] = pRight[iRightIndex++];  
46.             continue;  
47.         }  
48.   
49.         //调用比较函数  
50.         if(func(pLeft[iLeftIndex], pRight[iRightIndex]))  
51.         {  
52.             pArray[iFinalIndex] = pLeft[iLeftIndex++];  
53.         }  
54.         else  
55.         {  
56.             pArray[iFinalIndex] = pRight[iRightIndex++];  
57.         }  
58.     }  
59. }  
60.   
61. template<typename T, class CompareFunc>  
62. void MergeSort(T *pArray, int iLow, int iHigh, CompareFunc func)  
63. {  
64.     //如果只有一个元素，直接退出  
65.     if(iLow == iHigh)  
66.     {  
67.         return;  
68.     }  
69.   
70.     //递归  
71.     int iMid = (iLow + iHigh) / 2;  
72.     MergeSort(pArray, iLow, iMid, func);  
73.     MergeSort(pArray, iMid + 1, iHigh, func);  
74.   
75.     //合并  
76.     Merge(pArray, iLow, iMid, iHigh, func);  
77. }  
78.   
79. template<typename T>  
80. void PrintArray(const T *pArray, int iSize)  
81. {  
82.     for(int i = 0; i < iSize; i++)  
83.     {  
84.         cout << pArray[i] << "--";  
85.     }  
86.   
87.     cout << endl;  
88. }  
89.   
90. int _tmain(int argc, _TCHAR* argv[])  
91. {  
92.     int arrTest[10] = {5, 2, 4, 8, 1,10, 9, 6, 3, 7};  
93.   
94.     cout<<"Original Array:" << endl;  
95.     PrintArray(arrTest, 10);  
96.   
97.     //升序排列  
98.     MergeSort(arrTest, 0, 9, ElemAsc<int>);  
99.     cout<<"Sort Asc:"<<endl;  
100.     PrintArray(arrTest, 10);  
101.   
102.     //降序排列  
103.     MergeSort(arrTest, 0, 9, ElemDesc<int>);  
104.     cout<<"Sort Desc:"<<endl;  
105.     PrintArray(arrTest, 10);  
106.       
107.     return 0;  
108. }