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 }