C++/GoLang如何实现自底向上的归并排序-创新互联

前言

10年积累的成都网站建设、网站建设经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站制作后付款的网站建设流程，更有广安免费网站建设让你可以放心的选择与我们合作。

上一篇文章写了一个自顶向下的归并排序，把一个完整的数组不断二分，然后再合并。其实换一种思路：把数组中相邻的N个元素看成是已经二分好了的，直接进行合并，就省掉了二分那一步骤

自底向上的归并排序示意图

C++实现:

template
void mergeSortButton2Top(T arr[], int n) {
 for (int size = 1; size <= n; size += size) {
 for (int i = 0; i+size < n; i+=2*size) //对[i,i+size-1]和[i+size,i+2*size-1]进行归并
  __merge(arr, i, i + size - 1, min(i + size + size - 1,n-1));// arr left mid right 如果i+2*size>n了，越界了，就取n-1
 }
}

template
void __merge(T arr[], int left, int mid, int right) { //将arr[left,mid] 和 arr[mid+1,right] 两部分进行归并

 T *tmp=new T[right-left+1];
 for (int i = left; i <= right; i++)
 tmp[i - left] = arr[i]; //先把arr（需要合并的左右片段） 复制给tmp

 int i = left, j = mid + 1; // i 做为左半部分的指针 j作为右半部分的指针
 for (int k = left; k <= right; k++) {
 if (i > mid) { // 左半部分 已经合入完了，将右半部分剩下的 全部合入
  arr[k] = tmp[j - left];
  j++;
 }
 else if (j > right) { // 右半部分 已经合入完了，将左半部分剩下的 全部合入
  arr[k] = tmp[i - left];
  i++;
 }
 else if (tmp[i - left] < tmp[j - left]) {
  arr[k] = tmp[i - left];
  i++;
 }
 else {
  arr[k] = tmp[j - left];
  j++;
 }
 }
 delete[] tmp;
}

int main() {
 int arr[9] = { 1,5,6,78,12,5,1,12,54 };
 mergeSortButton2Top(arr,9);
 for (int i = 0; i < 9; i++) {
 cout << arr[i]<<" ";
 }
 return 0;
}

当前标题：C++/GoLang如何实现自底向上的归并排序-创新互联
文章URL：http://www.cdkjz.cn/article/esejg.html