生成初始?xì)w并段算法的目的是減少初始?xì)w并段個(gè)數(shù)降低歸并趟數(shù)和磁盤(pán)讀寫(xiě)次數(shù)提高外部排序歸并效率該生成算法在數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蟮姆椒ê蚦語(yǔ)言描述 第二版 殷人昆著 10.3.3節(jié)有詳細(xì)描述本文給出的該算法的C代碼是:#includeiostream#includevectorusingnamespacestd;templatetypenameTvoidadjust(vectorsize_tloser_tree,vectorTkey,vectorsize_tsegment_index,size_t start,size_t fathest_leaf_num,size_t offset,vectorboolinfinity){size_t curstart1;size_t parent;if(curfathest_leaf_num){parent(curoffset)/2;}else{parent(cur-fathest_leaf_numkey.size()-1)/2;}--cur;while(parent0){boolvictoryfalse;if(loser_tree[parent]!segment_index.size()cur!segment_index.size()){if(segment_index[loser_tree[parent]]segment_index[cur]){victorytrue;}elseif(segment_index[loser_tree[parent]]segment_index[cur]){if(infinity[loser_tree[parent]]false){if(infinity[cur]||key[loser_tree[parent]]key[cur]){victorytrue;}}}}else{if(cur!segment_index.size()){victorytrue;}}if(victory){size_t tempcur;curloser_tree[parent];loser_tree[parent]temp;}parent/2;}loser_tree[0]cur;}templatetypenameTvoidexteranlSort(vectorvectorTmerge_segment,vectorTinput,size_t merge_paths){size_t k1;while(k1merge_paths-1){k1;}size_t offset(k1)-1;size_t farthest_nummerge_paths-k;size_t fathest_leaf_num2*farthest_num;vectorsize_tloser_tree(merge_paths);vectorTkey(merge_paths);vectorsize_tsegment_index(merge_paths);vectorboolinfinity(key.size(),false);for(size_t i0;iloser_tree.size();i){loser_tree[i]segment_index.size();}size_t run0;for(size_t i0;ikey.size();i){if(runinput.size()){infinity[i]true;segment_index[i]2;}else{key[i]input[run];segment_index[i]1;}adjust(loser_tree,key,segment_index,i,fathest_leaf_num,offset,infinity);}T last_key;size_t pre_segement_index0;while(infinity[loser_tree[0]]false){if(segment_index[loser_tree[0]]!pre_segement_index){merge_segment.push_back(vectorT());pre_segement_index;}merge_segment.back().push_back(key[loser_tree[0]]);last_keykey[loser_tree[0]];if(runinput.size()){segment_index[loser_tree[0]]pre_segement_index1;infinity[loser_tree[0]]true;}else{if(input[run]last_key){segment_index[loser_tree[0]]pre_segement_index1;}else{segment_index[loser_tree[0]]pre_segement_index;}key[loser_tree[0]]input[run];}adjust(loser_tree,key,segment_index,loser_tree[0],fathest_leaf_num,offset,infinity);}}intmain(){vectorintinput{17,21,5,44,10,12,56,32,29};vectorvectorintresult;exteranlSort(result,input,3);for(size_t i0;iresult.size();i){cout第i1個(gè)歸并段endl;for(constautorun:result[i]){coutrun ;}coutendl;}return0;}