數(shù)據(jù)結(jié)構(gòu)6.5歸并排序主講人：朱利華常州信息職業(yè)技術(shù)學(xué)院歸并排序歸并：將兩個(gè)有序數(shù)列合并成一個(gè)有序數(shù)列建立在歸并操作上的一種有效的排序算法采用分治法：將已有序的子序列合并，得到完全有序序列；即先使每個(gè)子序列有序，再使子序列段間有序。什么是歸并排序歸并排序多路歸并2-路歸并方式自底往上自頂往下歸并排序分類數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院(1)自頂向下的歸并排序算法思路

把待排序列不斷的二分，直到子序列元素個(gè)數(shù)為一個(gè)然后再將兩個(gè)有序序列合并成一個(gè)新的有序序列兩個(gè)新的有序序列又可以合并成另一個(gè)新的有序序列以此類推，直到合并成一個(gè)有序的序列一般用遞歸來實(shí)現(xiàn)基本思路歸并排序數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院基本思路歸并排序(1)自頂向下的歸并排序步驟：分解:分解待排序的n個(gè)元素序列為各具n/2個(gè)元素的子序列；解決:使用歸并排序遞歸地對(duì)子序列排序；合并:合并兩個(gè)已排序的子序列。數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院(2)自底向上的歸并排序算法思路:先將待排序列中的元素分成n個(gè)長(zhǎng)度為1的子序列;然后將這些子序列兩兩合并成有序序列，兩兩有序的序列歸并成n/4個(gè)長(zhǎng)度為4的有序序列;以此類推，直到歸并的長(zhǎng)度等于整個(gè)數(shù)組長(zhǎng)度，此時(shí)整個(gè)序列有序。一般用循環(huán)來實(shí)現(xiàn)堆相關(guān)概念歸并排序示例【例6-9】設(shè)待排序序列有8個(gè)記錄，其關(guān)鍵字分別為：{26，53，48，11，13，48，32，15}。寫出使用自頂向下歸并排序方法進(jìn)行排序的過程。歸并排序2653481113483215初始265348111348321526534811134832152653481113483215一次分解二次分解三次分解解決2653114813481532一次歸并1126485313153248二次歸并終止1113152632484853治分示例【例6-10】設(shè)待排序序列8個(gè)記錄，其關(guān)鍵字分別為：{26，53，48，11，13，48，32，15}。寫出使用自底向下歸并排序方法進(jìn)行排序的過程。歸并排序2653481113483215初始兩兩歸并四四歸并八八歸并265311481348153211264853131532481113152632484853“分”：把原數(shù)組劃分成兩個(gè)子數(shù)組的過程“治”：將兩個(gè)有序數(shù)組合并成一個(gè)更大的有序數(shù)組基本操作歸并排序數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院(1)自頂向下歸并排序設(shè)當(dāng)前區(qū)間R[low...high]，分治法步驟：分解：將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn)mid=[(low+high)/2]；求解：遞歸地對(duì)兩個(gè)子區(qū)間R[low...mid]和R[mid+1...high]進(jìn)行歸并排序；組合：將已排序兩個(gè)子區(qū)間R[low...mid]和R[mid+1...high]歸并為一個(gè)有序區(qū)間R[low...high]。遞歸終結(jié)條件：子區(qū)間長(zhǎng)度為1。算法描述歸并排序(2)自底向上歸并排序第1趟，將待排序序列R[1...n]看作是n個(gè)長(zhǎng)度為1的有序序列，將這些子序列兩兩歸并：若n為偶數(shù)，則得到n/2個(gè)長(zhǎng)度為2的有序子文件；若n為奇數(shù)，則最后一個(gè)子文件輪空（不參與歸并）。再將合并后的n/2（或者n/2+1）個(gè)子序列繼續(xù)兩兩合并；以此類推，得到一個(gè)完整的有序序列。算法描述歸并排序算法實(shí)現(xiàn)—自頂向下歸并排序歸并排序//自頂向下歸并排序publicstaticvoidupToDownMergeSort(inta[]){upToDownMergeSort(0,a.length-1,a);}//自頂向下歸并排序核心算法publicstaticvoidmergeSort(intlow,inthigh,inta[]){if(low<high){intmid=(low+high)/2;//分解 mergeSort(low,mid,a);//遞歸調(diào)用，對(duì)左邊排序 mergeSort(mid+1,high,a);//遞歸調(diào)用，對(duì)右邊排序 //調(diào)用合并方法，將兩個(gè)有序序列合并為一個(gè)有序序列merge(low,mid,high,a);}}//合并兩個(gè)序列

publicstaticvoidmerge(intlow,intmid,inthigh,inta[]){intb[]=newint[a.length];//建立轉(zhuǎn)存數(shù)組

//f為第一個(gè)數(shù)組索引，s為第二個(gè)數(shù)組索引，p為b數(shù)組索引intf=low,s=mid+1,p=low;

while(f<=mid&&s<=high){//兩個(gè)數(shù)組中值小的，放入b中 if(a[f]<=a[s]){ b[p]=a[f];f++;}else{ b[p]=a[s];s++;} p++;}if(f==mid+1)//若第一個(gè)數(shù)組全部存入，則將第二個(gè)數(shù)組中

的剩余元素全部存入b中 for(;s<=high&&p<=high;p++,s++)b[p]=a[s];else//否則將第一個(gè)數(shù)組全部存入b中for(;f<=mid&&p<=high;p++,f++)b[p]=a[f];for(inti=low;i<=high;i++) a[i]=b[i];}算法實(shí)現(xiàn)—自底向上歸并排序歸并排序//自底向上歸并排序publicstaticvoidbottomToUpMergeSort(inta[]){inti,s,t=1;while(t<a.length-1){s=t;t=2*s;i=0;for(;i+t<a.length;i+=t)merge(i,i+s-1,i+t-1,a);//自底向上進(jìn)行排序

if(i+s-1<a.length-1)//判斷是否有落單元素merge(i,i+s-1,a.length