每個人都曾試圖在平淡的學(xué)習(xí)、工作和生活中寫一篇文章。寫作是培養(yǎng)人的觀察、聯(lián)想、想象、思維和記憶的重要手段。范文怎么寫才能發(fā)揮它最大的作用呢？下面是小編為大家收集的優(yōu)秀范文，供大家參考借鑒，希望可以幫助到有需要的朋友。
自頂向下的歸并排序 自底向上求最優(yōu)解篇一
積極向上的文章
推薦度：
樂觀向上的優(yōu)生評語
推薦度：
蘇格拉底的故事
推薦度：
實(shí)現(xiàn)中國夢感悟
推薦度：
積極向上的正能量文案
推薦度：
相關(guān)推薦
既然有c++實(shí)現(xiàn)自頂向下的歸并排序算法，當(dāng)然也有c++實(shí)現(xiàn)自底向上的歸并排序算法啦。下面小編為大家整理了c++實(shí)現(xiàn)自底向上的歸并排序算法，希望能幫到大家！
自底向上的歸并排序：歸并排序主要是完成將若干個有序子序列合并成一個完整的有序子序列；自底向上的排序是歸并排序的一種實(shí)現(xiàn)方式，將一個無序的n長數(shù)組切個成n個有序子序列，然后再兩兩合并，然后再將合并后的n/2（或者n/2 + 1）個子序列繼續(xù)進(jìn)行兩兩合并，以此類推得到一個完整的'有序數(shù)組。下圖詳細(xì)的分解了自底向上的合并算法的實(shí)現(xiàn)過程：
/*=============================================================================## ?filename: mergesort.c# ?algorithm: 歸并排序（自底向上）# ?author: ?knife# ?created: 2014-06-14 16:40:02#=============================================================================*/#include#includevoid merge_sort(int* intarr, int intarr_len);void merge_array(int* intarr1, int len1, int* intarr2, int len2);void main(){ int intarr[] = {8,3,6,4,2,9,5,4,1,7}; int n = sizeof (intarr) / sizeof (intarr[0]); int i = 0; merge_sort(intarr, n); for(;i<n;i++){ ?printf("%d ",intarr[i]); } printf("n");}//歸并排序（自底向上）void merge_sort(int* intarr, int intarr_len){ int len = 1; int k = 0; while (len < intarr_len) { ? int i = 0; ? for (; i + 2*len <= intarr_len; i += 2*len){ ? int* intarr1 = intarr + i; ? int intarr1_len = len; ? int* intarr2 = intarr + i + len; ? int intarr2_len = len; ? merge_array(intarr1, intarr1_len, intarr2, intarr2_len); ? } ?if (i + len <= intarr_len){ ? ?int* intarr1 = intarr + i; ? int intarr1_len = len; ? int* intarr2 = intarr + i + len; ? int intarr2_len = intarr_len - i - len; ? merge_array( intarr1, intarr1_len, intarr2, intarr2_len); ? } ?len *= 2; //有序子序列長度*2 ?} }//合并兩個數(shù)組，并排序void merge_array(int* intarr1, int len1, int* intarr2, int len2){ //申請分配空間 int* list = (int*) malloc((len1+len2) * sizeof (int)); int i = 0, j = 0, k = 0; while(i < len1 && j < len2){ ? // 把較小的那個數(shù)據(jù)放到結(jié)果數(shù)組里， 同時移動指針 ?list[k++] = (intarr1[i] < intarr2[j]) ? intarr1[i++] : intarr2[j++]; } // 如果 intarr1 還有元素，把剩下的數(shù)據(jù)直接放到結(jié)果數(shù)組 while(i < len1){ ?list[k++] = intarr1[i++]; } // 如果 intarr2 還有元素，把剩下的數(shù)據(jù)直接放到結(jié)果數(shù)組 while(j < len2){ ?list[k++] = intarr2[j++]; } ?// 把結(jié)果數(shù)組 copy 到 intarr1 里 for(i = 0; i < k; i++){ ?intarr1[i] = list[i]; } //釋放申請的空間 free(list);}
平均時間復(fù)雜度：o(nlog2n)
空間復(fù)雜度：o(n) (用于存儲有序子序列合并后有序序列)
穩(wěn)定性：穩(wěn)定
s("content_relate");【c++實(shí)現(xiàn)自底向上的歸并排序算法】相關(guān)文章：
c++實(shí)現(xiàn)自頂向下的歸并排序算法
10-01
c++歸并排序算法實(shí)例
09-26
c語言實(shí)現(xiàn)歸并排序算法實(shí)例
11-21
c++插入排序算法實(shí)例
09-25
c++實(shí)現(xiàn)一維向量旋轉(zhuǎn)算法
10-07
java簡單選擇排序算法及實(shí)現(xiàn)
12-01
希爾排序算法的c語言實(shí)現(xiàn)示例
10-04
快速排序算法及c#版的實(shí)現(xiàn)示例
09-30
6種常見的排序算法的c語言實(shí)現(xiàn)
10-04
