归并排序（自顶向下？自底向上？）

 1 #include <iostream>
 2 #include <cstdlib>
 3 
 4 #define ARR_SIZE 20
 5 #define MIN(x, y) (x)>(y)?(y):(x) 
 6 using namespace std;
 7 
 8 int kk= 0;
 9 
10 void mergeBUsort(int a[]);
11 void merge(int a[], int lo, int mid, int hi);
12 void CreateRandArr(int a[]);
13 void exchange(int *a, int *b);
14 
15 int main()
16 {
17     int a[ARR_SIZE];
18     int i;
19     CreateRandArr(a);
20     mergeBUsort(a);
21     cout << "after sort: " << endl;
22     for(i=0;i<ARR_SIZE;i++)
23     {
24         cout << a[i] << ' ' ;
25     }
26     
27     return 0;
28 }
29 
30 void mergeBUsort(int a[])   
31 {
32     int sz=1;
33     for(sz=1; sz < ARR_SIZE; sz+=sz)
34     {
35         /* 下面的for循环为什么是 ARR_SIZE - sz 而不是 ARR_SIZE - 2sz：如果是后者的话则数组的最后一段就不能排序了，之所以lo>ARR_SIZE - 2sz还能继续归并，
36         意思是虽然我后面的元素不足2sz个了，但这后面不足2sz个的元素依然可以分为1点几个序列（一个有序序列有sz个元素），依然要归并为1个序列
37         而当后面的元素不足sz个时，也就是不到一个sz序列的长度，说明剩下的这不到sz个元素本身就是有序的，所以不用进行归并 */
38         for(int lo = 0;lo<ARR_SIZE - sz;lo+=2*sz)   
39         {
40             merge(a, lo, lo+sz-1, MIN(lo+2*sz-1, ARR_SIZE-1));  /* 因为下一次归并lo是从2sz开始，所以这里hi取lo+2*sz-1而不是lo+2*sz */
41         }
42     }
43 }
44 
45 void merge(int a[], int lo, int mid, int hi)
46 {
47     int i, j=0, k=lo;  /* 对于递归调用的函数，千万要注意：每次递归调用里的参数每次取的都是对应当次递归的值！例如这里的k值，每次应该赋值为lo而不是0！这个错误很容易犯 */
48     int ap[hi+1];
49     for(i=0;i<=hi;i++)
50     {
51         ap[i] = a[i];
52     }
53     i = lo;
54     j = mid+1;
55     while(k<=hi)
56     {
57         if(i > mid)a[k] = ap[j++];
58         else if(j > hi)a[k] = ap[i++]; 
59         else if(ap[i] <= ap[j]) a[k] = ap[i++];
60         else if(ap[i] > ap[j]) a[k] = ap[j++];
61         k++;
62     }
63 
64     cout << "No."<< kk++ << endl;
65 }
66 
67 void CreateRandArr(int a[])
68 {
69     int i;
70     for(i=0;i<ARR_SIZE;i++)
71     {
72         a[i] = rand() % 100;
73         cout <<a[i] << ' ' ; 
74     }
75     cout << endl;
76 }
77 
78 void exchange(int *a, int *b)
79 {
80     int temp;
81     temp = *a;
82     *a = *b;
83     *b = temp;
84 }

另一种？

 1 #include <iostream>
 2 #include <cstdlib>
 3 
 4 #define ARR_SIZE 20
 5 
 6 using namespace std;
 7 
 8 int kk= 0;
 9 
10 void mergesort(int a[], int lo, int hi);
11 void merge(int a[], int lo, int mid, int hi);
12 void CreateRandArr(int a[]);
13 void exchange(int *a, int *b);
14 
15 int main()
16 {
17     int a[ARR_SIZE];
18     int i;
19     CreateRandArr(a);
20     mergesort(a, 0, ARR_SIZE -1);
21     cout << "after sort: " << endl;
22     for(i=0;i<ARR_SIZE;i++)
23     {
24         cout << a[i] << ' ' ;
25     }
26     
27     return 0;
28 }
29 
30 void mergesort(int a[], int lo, int hi)   
31 {
32     if(lo >= hi) return;   /* 如果这里没有等于的话，会陷入无限递归 */
33     int mid = lo + (hi -lo)/2;
34     mergesort(a, lo, mid);
35     mergesort(a, mid+1, hi);
36     merge(a, lo, mid, hi);
37 }
38 
39 void merge(int ar[], int lo, int mid, int hi)
40 {
41     int ap[ARR_SIZE];
42     /* 注意下面这三个变量的赋值，对于递归调用的函数，千万要注意：每次递归调用里的参数每次取的都是对应当次递归的值！
43     每次merge操作的只是ar数组中的一部分而不是整个数组，例如这里的m值，每次应该赋值为lo而不是0！这个错误很容易犯 */
44     int i=lo,j=mid+1,m=lo;    
45     for(int k=0;k<ARR_SIZE;k++)   /* 其实这里的ap可以放在外面声明，否则每次都要声明一遍，拷贝也只拷贝lo到hi的值就可以了 */
46     {
47         ap[k] = ar[k];
48     }
49     while(m<=hi)
50     {
51         if(i>mid)ar[m++]=ap[j++];
52         else if(j>hi)ar[m++] = ap[i++];
53         else if(ap[i]< ap[j])ar[m++] = ap[i++];
54         else ar[m++] = ap[j++];
55     }
56 
57 
58 }
59 
60 void CreateRandArr(int a[])
61 {
62     int i;
63     for(i=0;i<ARR_SIZE;i++)
64     {
65         a[i] = rand() % 100;
66         cout <<a[i] << ' ' ; 
67     }
68     cout << endl;
69 }
70 
71 void exchange(int *a, int *b)
72 {
73     int temp;
74     temp = *a;
75     *a = *b;
76     *b = temp;
77 }