2、归并排序

　　归并排序采用了算法设计中的分治法，分治法的思想是将原问题分解成n个规模较小而结构与原问题相似的小问题，递归的解决这些子问题，然后再去合并其结果，得到原问题的解。分治模式在每一层递归上有三个步骤：

分解（divide）：将原问题分解成一系列子问题。

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

合并（combine）：将子问题的结果合并成原问题的解。

归并排序（merge sort）算法按照分治模式，操作如下：

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

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

合并：合并两个已排序的子序列以得到排序结果

　　在对子序列排序时，长度为1时递归结束，单个元素被视为已排序好的。归并排序的关键步骤在于合并步骤中的合并两个已经有序的子序列，引入了一个辅助过程，merge(A,p,q,r)，将已经有序的子数组A[p...q]和A[q+1...r]合并成为有序的A[p...r]。书中给出了采用哨兵实现merge的伪代码，课后习题要求不使用哨兵实现merge过程。在这个两种方法中都需要引入额外的辅助空间，用来存放即将合并的有序子数组，总的空间大小为n。现在用C语言完整实现这两种方法，程序如下：
1 //采用哨兵实现merge
2 #define MAXLIMIT 65535
3 void merge(int datas,int p,int q,int r)
4 {
5 int n1 = q-p+1; //第一个有序子数组元素个数
6 int n2 = r-q; //第二个有序子数组元素个数
7 int *left = (int)malloc(sizeof(int)(n1+1));
8 int *right = (int)malloc(sizeof(int)(n2+1));
9 int i,j,k;
10 //将子数组复制到临时辅助空间
11 for(i=0;i<n1;++i)
12 left[i] = datas[p+i];
13 for(j=0;j<n2;++j)
14 right[j] = datas[q+j+1];
15 //添加哨兵
16 left[n1] = MAXLIMIT;
17 right[n2] = MAXLIMIT;
18 //从第一个元素开始合并
19 i = 0;
20 j = 0;
21 //开始合并
22 for(k=p;k<=r;k++)
23 {
24 if(left[i] < right[j])
25 {
26 datas[k] = left[i];
27 i++;
28 }
29 else
30 {
31 datas[k] = right[j];
32 j++;
33 }
34 }
35 free(left);
36 free(right);
37 }
不采用哨兵实现，需要考虑两个子数组在合并的过程中哪一个先合并结束，剩下的那个子数组剩下部分复制到数组中，程序实现如下：
1 int merge(int *datas,int p,int q,int r)
2 {
3 int n1 = q-p+1;
4 int n2 = r-q;
5 int *left = (int)malloc(sizeof(int)(n1+1));
6 int *right = (int)malloc(sizeof(int)(n2+1));
7 int i,j,k;
8 memcpy(left,datas+p,n1sizeof(int));
9 memcpy(right,datas+q+1,n2*sizeof(int));
10 i = 0;
11 j = 0;
12 for(k=p;k<=r;++k)
13 {
14 if(i <n1 && j< n2) //归并两个子数组
15 {
16 if(left[i] < right[j])
17 {
18 datas[k] = left[i];
19 i++;
20 }
21 else
22 {
23 datas[k] = right[j];
24 j++;
25 }
26 }
27 else
28 break;
29 }
30 //将剩下的合并到数组中
31 while(i != n1)
32 datas[k++] = left[i++];
33 while(j != n2)
34 datas[k++] = right[j++];
35 free(left);
36 free(right);
37 }
merge过程的运行时间是θ(n)，现将merge过程作为归并排序中的一个子程序使用，merge_sort(A,p,r),对数组A[p...r]进行排序
归并排序算法分析：
　　算法中含有对其自身的递归调用，其运行时间可以用一个递归方程（或递归式）来表示。归并排序算法分析采用递归树进行，递归树的层数为lgn+1，每一层的时间代价是cn，整棵树的代价是cn(lgn+1)=cnlgn+cn，忽略低阶和常量c，得到结果为θ(nlg n)。

3、课后习题

　　有地道题目比较有意思，认真做了做，题目如下：

方法1：要求运行时间为θ（nlgn），对于集合S中任意一个整数a，设b=x-a，采用二分查找算法在S集合中查找b是否存在，如果b存在说明集合S中存在两个整数其和等于x。而二分查找算起的前提是集合S是有序的，算法时间为θ（lgn），因此先需要采用一种时间最多为θ(nlgn)的算法对集合S进行排序。可以采用归并排序算法，这样总的运行时间为θ（nlgn），满足题目给定的条件。

具体实现步骤：

1、采用归并排序算法对集合S进行排序

2、对集合S中任意整数a，b=x-a，采用二分查找算法b是否在集合S中，若在则集合S中存在两个整数其和等于x，如果遍历了S中所有的元素，没能找到b，即集合S中不存在两个整数其和等于x。

采用C语言实现如下：

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 //非递归二叉查找
6 int binary_search(int datas,int length,int obj)
7 {
8 int low,mid,high;
9 low = 0;
10 high = length;
11 while(low < high)
12 {
13 mid = (low + high)/2;
14 if(datas[mid] == obj)
15 return mid;
16 else if(datas[mid] > obj)
17 high = mid;
18 else
19 low = mid+1;
20 }
21 return -1;
22 }
23
24 //递归形式二分查找
25 int binary_search_recursive(int *datas,int beg,int end,int obj)
26 {
27 int mid;
28 if(beg < end)
29 {
30 mid = (beg+end)/2;
31 if(datas[mid] == obj)
32 return mid;
33 if(datas[mid] > obj)
34 return binary_search_recursive(datas,beg,mid,obj);
35 else
36 return binary_search_recursive(datas,mid+1,end,obj);
37
38 }
39 return -1;
40 }
41 //合并子程序
42 int merge(int *datas,int p,int q,int r)
43 {
44 int n1 = q-p+1;
45 int n2 = r-q;
46 int *left = (int)malloc(sizeof(int)(n1+1));
47 int *right = (int)malloc(sizeof(int)(n2+1));
48 int i,j,k;
49 memcpy(left,datas+p,n1sizeof(int));
50 memcpy(right,datas+q+1,n2*sizeof(int));
51 i = 0;
52 j = 0;
53 for(k=p;k<=r;++k)
54 {
55 if(i <n1 && j< n2)
56 {
57 if(left[i] < right[j])
58 {
59 datas[k] = left[i];
60 i++;
61 }
62 else
63 {
64 datas[k] = right[j];
65 j++;
66 }
67 }
68 else
69 break;
70 }
71 while(i != n1)
72 datas[k++] = left[i++];
73 while(j != n2)
74 datas[k++] = right[j++];
75 free(left);
76 free(right);
77 }
78 //归并排序
79 void merge_sort(int *datas,int beg,int end)
80 {
81 int pos;
82 if(beg < end)
83 {
84 pos = (beg+end)/2;
85 merge_sort(datas,beg,pos);
86 merge_sort(datas,pos+1,end);
87 merge(datas,beg,pos,end);
88 }
89 }
90
91 int main(int argc,char *argv[])
92 {
93 int i,j,x,obj;
94 int datas[10] = {34,11,23,24,90,43,78,65,90,86};
95 if(argc != 2)
96 {
97 printf("input error.\n");
98 exit(0);
99 }
100 x = atoi(argv[1]);
101 merge_sort(datas,0,9);
102 for(i=0;i<10;i++)
103 {
104 obj = x - datas[i];
105 j = binary_search_recursive(datas,0,10,obj);
106 //j = binary_search(datas,10,obj);
107 if( j != -1 && j!= i) //判断是否查找成功
108 {
109 printf("there exit two datas (%d and %d) which their sum is %d.\n",datas[i],datas[j],x);
110 break;
111 }
112 }
113 if(i==10)
114 printf("there not exit two datas whose sum is %d.\n",x);
115 exit(0);
116 }

方法2具体思想如下：

1、对集合S进行排序，可以采用归并排序算法

2、对S中每一个元素a，将b=x-a构造一个新的集合S'，并对S’进行排序

3、去除S和S'中重复的数据

4、将S和S'按照大小进行归并，组成新的集合T，若干T中有两队及以上两个连续相等数据，说明集合S中存在两个整数其和等于x。

例如：S={7,10,5,4,2,5}，设x=11，执行过程如下：

对S进行排序，S={2,4,5,5,7,10}。

S'={9,7,6,6,4,1},排序后S’={1,4,6,6,7,9}。

去除S和S'中重复的数据后S={2,4,5,7,10}，S'={1,4,6,7,9}

归纳S和S'组成新集合T={1,2,4,4,5,6,7,7,9,10}，可以看出集合T中存在两对连续相等数据4和7，二者存在集合S中，满足4+7=11。