7-5歸并排序v第七章排序技術(shù)學(xué)什么？二路歸并排序的遞歸實(shí)現(xiàn)二路歸并排序的非遞歸實(shí)現(xiàn)提出關(guān)鍵問題給出解決方法寫出算法描述得到完整算法運(yùn)行實(shí)例7-5-1二路歸并排序的遞歸實(shí)現(xiàn)v第七章排序技術(shù)基本思想二路歸并排序的基本思想：將待排序序列劃分為兩個長度相等的子序列，分別對這兩個子序列進(jìn)行排序，得到兩個有序子序列，再將這兩個有序子序列合并成一個有序序列。r1rn/2…rn…rn/2+1劃分r1'rn/2'≤…

≤rn'rn/2+1'≤…

≤r1''rn/2''≤…

≤rn''rn/2+1''≤…

≤≤運(yùn)行實(shí)例2420101812待排序序列16劃分242010181216分別排序101224161820合并101216182024一次合并：合并兩個相鄰的有序子序列20254050152130合并可以就地進(jìn)行嗎？ijk

temp[]15

算法描述：while(i<=last1&&j<=last2){if(data[i]<=data[j])temp[k++]=data[i++];elsetemp[k++]=data[j++];}first1last1last1+1last2data[]關(guān)鍵問題如何表示兩個相鄰的子序列？某個子序列比較完畢，做什么？算法描述：while(i<=last1)temp[k++]=data[i++];while(j<=last2)temp[k++]=data[j++];202130

4050

算法實(shí)現(xiàn)voidSort::Merge(intfirst1,intlast1,intlast2){int*temp=newint[length];inti=first1,j=last1+1,k=first1;while(i<=last1&&j<=last2){if(data[i]<=data[j])temp[k++]=data[i++];elsetemp[k++]=data[j++];}while(i<=last1)temp[k++]=data[i++];while(j<=last2)temp[k++]=data[j++];for(i=first1;i<=last2;i++)data[i]=temp[i];delete[]temp;}遞歸算法voidSort::MergeSortRecusion(intfirst,intlast){if(first==last)return;else{intmid=(first+last)/2;MergeSort1(first,mid);MergeSort1(mid+1,last);Merge(first,mid,last);}}r1rn/2…rn…rn/2+1劃分r1'rn/2'≤…

≤rn'rn/2+1'≤…

≤r1''rn/2''≤…

≤rn''rn/2+1''≤…

≤≤7-5-2

二路歸并排序的非遞歸實(shí)現(xiàn)v第七章排序技術(shù)執(zhí)行過程252040153010182025251540203010181540103018待排序序列第一趟歸并結(jié)果第二趟歸并結(jié)果第三趟歸并結(jié)果1520254010183010151820253040構(gòu)造初始有序子序列子序列長度有什么規(guī)律？在一趟歸并中有幾種情況？一趟歸并設(shè)i

指向待歸并序列的第一個記錄，歸并的步長是2h情況1：i+2h≤n，則相鄰兩個有序子序列的長度均為hihhi+2hnwhile(i+2*h<=length){Merge(i,i+h-1,i+2*h-1);i=i+2*h;}算法描述：voidSort::Merge(intfirst1,intlast1,intlast2)子序列長度有什么規(guī)律？在一趟歸并中有幾種情況？情況2：i+h＜n，則相鄰有序子序列一個長度為h，另一個長度小于hif(i+h<length)

Merge(i,i+h-1,length-1);算法描述：hii+hn<h一趟歸并設(shè)i

指向待歸并序列的第一個記錄，歸并的步長是2h子序列長度有什么規(guī)律？在一趟歸并中有幾種情況？voidSort::Merge(intfirst1,intlast1,intlast2)情況3：i

+h≥

n，則表明只剩下一個有序子序列算法實(shí)現(xiàn)voidSort::MergePass(inth){inti=0;while(i+2*h<=length){Merge(i,i+h-1,i+2*h-1);i=i+2*h;}if(i+h<length)

Merge(i,i+h-1,length-1);}如何控制二路歸并的結(jié)束？子序列長度有什么規(guī)律？voidSort::MergeSort(){inth=1;while(h<length){MergePass(h);h=2*h;}}25204015202525154020154015202540時間性能執(zhí)行趟數(shù)：log2n每一趟：將記錄掃描一遍，O(n)最好、最壞、平均情況：O(nlog2n)二路歸并執(zhí)行多少趟？每一趟的時間性能是多少？空間性能：合并不能就地進(jìn)行，O(n)穩(wěn)定性：穩(wěn)定如果將判斷條件改為(r[i]<r[j])，仍然是穩(wěn)定的嗎？w