归并排序（自顶向下？自底向上？）
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 }
赞 (0)