生成初始归并段算法实现

生成初始归并段算法的目的是减少初始归并段个数降低归并趟数和磁盘读写次数提高外部排序归并效率该生成算法在数据结构:用面向对象的方法和c语言描述 第二版 殷人昆著 10.3.3节有详细描述本文给出的该算法的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个归并段endl;for(constautorun:result[i]){coutrun ;}coutendl;}return0;}