排序之自底向上?自顶向下?--C++
看着算法书有点懵T_T
参照https://blog.csdn.net/u011197534/article/details/78368580
自顶向下即是归并排序,参考我之前的归并排序,如图
自底向上,就是两两归并、四四归并、88归并,如下图:
书上的伪代码:
/* 输入:n个元素的数组A[1...n] 输出:按非降序排列的数组A[1...n] t <- 1 while t < n s <- t; t <- 2s; t <- 0 while i+t <= n merge(A, i+1, i+s, i+t) i <- i+t end while if i+s < n then merge(A, i+1, i+s, n) end while */
完整代码:
void merge(int A[], int l, int mid, int r) { int help[r-l+1]; //辅助数组 int i = 0; int lIndex = l; int rIndex = mid + 1; while(lIndex<=mid && rIndex<=r) { help[i++] = A[lIndex] < A[rIndex] ? A[lIndex++] : A[rIndex++]; } while(lIndex<=mid) { help[i++] = A[lIndex++]; } while(rIndex<=r) { help[i++] = A[rIndex++]; } for(i = 0; i < r-l+1; i++) { A[l+i] = help[i]; } } void downUpSort(int A[], int n) { int i = 1; while(i < n) //for(int i=1; i<n; t = 2 * i) { int s = i; i = 2 * s; //归并子数组序列扩大一倍 int j = 0; //子区间归并 while(i+j <= n) //for(int j = 0; j < n-i; j = j+2*i) { merge(A, j, j+s-1, j+i-1); j = j+i; } if(j+s < n) merge(A, j, j+s-1, n-1); } } int main() { int A[9] = {5,4,8,2,9,3,1,6,7}; cout << "before sort: "; for (int i = 0; i < 9; i++) cout << A[i] << " "; cout << endl; downUpSort(A, 9); cout << "after sort: "; for (int i = 0; i < 9; i++) cout << A[i] << " "; cout << endl; }
结果如下: