前言

10年積累的成都網(wǎng)站建設、網(wǎng)站建設經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先網(wǎng)站制作后付款的網(wǎng)站建設流程，更有廣安免費網(wǎng)站建設讓你可以放心的選擇與我們合作。

上一篇文章寫了一個自頂向下的歸并排序，把一個完整的數(shù)組不斷二分，然后再合并。其實換一種思路：把數(shù)組中相鄰的N個元素看成是已經(jīng)二分好了的，直接進行合并，就省掉了二分那一步驟

自底向上的歸并排序示意圖

C++實現(xiàn):

template<typename T>
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<typename T>
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) { // 左半部分 已經(jīng)合入完了，將右半部分剩下的 全部合入
  arr[k] = tmp[j - left];
  j++;
 }
 else if (j > right) { // 右半部分 已經(jīng)合入完了，將左半部分剩下的 全部合入
  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如何實現(xiàn)自底向上的歸并排序-創(chuàng)新互聯(lián)
文章起源：http://www.rwnh.cn/article26/esejg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、網(wǎng)站收錄、搜索引擎優(yōu)化、軟件開發(fā)、微信小程序、移動網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)