0004算法笔记

       合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序，合并排序也叫归并排序。

      1、递归实现的合并排序  

[cpp] view plaincopy

1. //2d7-1 递归实现二路归并排序  
2. #include "stdafx.h"  
3. #include <iostream>       
4. using namespace std;   
5.   
6. int a[] = {10,5,9,4,3,7,8};  
7. int b[7];  
8.   
9. template <class Type>  
10. void Merge(Type c[],Type d[],int l,int m,int r);  
11.   
12. template <class Type>  
13. void MergeSort(Type a[],int left,int right);  
14.   
15. int main()  
16. {  
17.     for(int i=0; i<7; i++)  
18.     {  
19.         cout<<a[i]<<" ";  
20.     }  
21.     cout<<endl;  
22.     MergeSort(a,0,6);  
23.     for(int i=0; i<7; i++)  
24.     {  
25.         cout<<a[i]<<" ";  
26.     }  
27.     cout<<endl;  
28. }  
29.   
30. template <class Type>  
31. void Merge(Type c[],Type d[],int l,int m,int r)  
32. {  
33.     int i = l,j = m + 1,k = l;  
34.     while((i<=m)&&(j<=r))  
35.     {  
36.         if(c[i]<=c[j])  
37.         {  
38.             d[k++] = c[i++];  
39.         }  
40.         else  
41.         {  
42.             d[k++] = c[j++];  
43.         }  
44.     }  
45.   
46.     if(i>m)  
47.     {  
48.         for(int q=j; q<=r; q++)  
49.         {  
50.             d[k++] = c[q];  
51.         }     
52.     }  
53.     else  
54.     {  
55.         for(int q=i; q<=m; q++)  
56.         {  
57.             d[k++] = c[q];  
58.         }  
59.     }  
60. }  
61.   
62. template <class Type>  
63. void MergeSort(Type a[],int left,int right)  
64. {  
65.     if(left<right)  
66.     {  
67.         int i = (left + right)/2;  
68.         MergeSort(a,left,i);  
69.         MergeSort(a,i+1,right);  
70.         Merge(a,b,left,i,right);//合并到数组b  
71.   
72.         //复制回数组a  
73.         for(int g=left; g<=right; g++)  
74.         {  
75.             a[g] = b[g];  
76.         }  
77.     }  
78. }  

       2、合并排序非递归实现

      从分支策略机制入手，可消除程序中的递归。非递归实现的大致思路是先将数组a中元素两两配对，用合并算法它们排序，构成n/2组长度为2的排好的子数组段，然后再将它们排成长度为4的排好序的子数组段，如此继续下去，直到整个数组排好序。

      程序代码如下：

[cpp] view plaincopy

1. //2d7-1 自然二路归并排序  
2. #include "stdafx.h"  
3. #include <iostream>       
4. using namespace std;   
5.   
6. int a[] = {10,5,9,4,3,7,8};  
7. int b[7];  
8.   
9. template <class Type>  
10. void Merge(Type c[],Type d[],int l,int m,int r);  
11.   
12. template <class Type>  
13. void MergePass(Type x[],Type y[],int s,int n);  
14.   
15. template <class Type>  
16. void MergeSort(Type a[],int n);  
17.   
18. int main()  
19. {  
20.     for(int i=0; i<7; i++)  
21.     {  
22.         cout<<a[i]<<" ";  
23.     }  
24.     cout<<endl;  
25.     MergeSort(a,7);  
26.     for(int i=0; i<7; i++)  
27.     {  
28.         cout<<a[i]<<" ";  
29.     }  
30.     cout<<endl;  
31. }  
32.   
33. template <class Type>  
34. void Merge(Type c[],Type d[],int l,int m,int r)  
35. {  
36.     int i = l,j = m + 1,k = l;  
37.     while((i<=m)&&(j<=r))  
38.     {  
39.         if(c[i]<=c[j])  
40.         {  
41.             d[k++] = c[i++];  
42.         }  
43.         else  
44.         {  
45.             d[k++] = c[j++];  
46.         }  
47.     }  
48.   
49.     if(i>m)  
50.     {  
51.         for(int q=j; q<=r; q++)  
52.         {  
53.             d[k++] = c[q];  
54.         }     
55.     }  
56.     else  
57.     {  
58.         for(int q=i; q<=m; q++)  
59.         {  
60.             d[k++] = c[q];  
61.         }  
62.     }  
63. }  
64.   
65. template <class Type>  
66. //合并大小为s的相邻子数组  
67. void MergePass(Type x[],Type y[],int s,int n)  
68. {  
69.     int i = 0;  
70.     while(i<=n-2*s)  
71.     {  
72.         //合并大小为s的相邻两段子数组  
73.         Merge(x,y,i,i+s-1,i+2*s-1);  
74.         i = i + 2*s;  
75.     }  
76.     //剩下的元素个数少于2s  
77.     if(i+s<n)  
78.     {  
79.         Merge(x,y,i,i+s-1,n-1);  
80.     }  
81.     else  
82.     {  
83.         for(int j=i; j<=n-1; j++)  
84.         {  
85.             y[j]=x[j];  
86.         }  
87.     }  
88. }  
89.   
90. template <class Type>  
91. void MergeSort(Type a[],int n)  
92. {  
93.     Type *b = new Type[n];  
94.     int s = 1;  
95.     while(s<n)  
96.     {  
97.         MergePass(a,b,s,n);//合并到数组b  
98.         s += s;  
99.         MergePass(b,a,s,n);//合并到数组a  
100.         s += s;  
101.     }  
102. }  

      程序清单中77至86行解释如下：当剩余元素少于2s时，分两种情况。

1、当i+s<n时，需要继续merge操作。例如：设s=4,n=13,i=8有如下图：

2、当i+s>=n时，剩余元素已排好序，直接复制。例如：设s=4,n=11，i=8有如下图：