數(shù)據(jù)結(jié)構(gòu)0409歸并排序課件

歸并排序歸并排序歸并排序“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。歸并排序“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新利用歸并的思想實(shí)現(xiàn)排序假設(shè)初始序列含有n個(gè)記錄，則可看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到?n/2?個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并，……，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止，這種排序方法稱為2-路歸并排序。利用歸并的思想實(shí)現(xiàn)排序假設(shè)初始序列含有n個(gè)記錄，則可看成是n例題初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]例題初始關(guān)鍵字：[49][38][65][97]算法思想2-路歸并排序?qū)[low..high]中的記錄歸并排序后放入T[low..high]中。當(dāng)序列長(zhǎng)度等于1時(shí)，遞歸結(jié)束，否則：（1）將當(dāng)前序列一分為二，求出分裂點(diǎn)mid=?(low+high)/2?;（2）對(duì)子序列R[low..mid]遞歸，進(jìn)行歸并排序，結(jié)果放入S[low..mid]中；算法思想2-路歸并排序?qū)[low..high]中的記錄歸并算法思想（3）對(duì)子序列R[mid+1..high]遞歸，進(jìn)行歸并排序，結(jié)果放入S[mid+1..high]中；（4）調(diào)用算法Merge，將有序的兩個(gè)子序列S[low..mid]和S[mid+1..high]歸并為一個(gè)有序的序列T[low..high]。算法思想（3）對(duì)子序列R[mid+1..high]遞歸，進(jìn)行算法描述voidMsort(RedTypeR[],RedType&T[],ints,intt){

//將R[s..t]歸并排序?yàn)門[s..t]if(s==t)T[s]=R[s];else{m=(s+t)/2;//將R[s..t]平分為R[s..m]和R[m+1..t]Msort(R,TR2,s,m);//遞歸地將R[s..m]歸并為有序的TR2[s..m]

Msort(R,TR2,m+1,t);//遞歸地R[m+1..t]歸并為有序的TR2[m+1..t]Merge(TR2,T,s,m,t);}//將TR2[s..m]和TR2[m+1..t]歸并到T[s..t]

}//Msort

算法描述voidMsort(RedTypeR[],算法描述

voidMergeSort(SqList&L){//對(duì)順序表L作2-路歸并排序

MSort(L.r,L.r,1,L.length);}//MergeSort算法描述

將兩個(gè)有序表歸并為一個(gè)新的有序表的算法

voidMerge(RedTypeR[],RedType&T[],inti,intm,intn){

//將有序的記錄序列R[i..m]和R[m+1..n]歸并為有序的記錄序列T[i..n]

intj,k;for(j=m+1,k=i;i<=m&&j<=n;++k){//將SR中記錄由小到大地并入TRifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)//TR[k..n]=SR[i..m];將剩余的SR[i..m]復(fù)制到TRwhile(k<=n&&i<=m)TR[k++]=SR[i++];if(j<=n)//將剩余的SR[j..n]復(fù)制到TRwhile(k<=n&&j<=n)TR[k++]=SR[j++];}//Merge將兩個(gè)有序表歸并為一個(gè)新的有序表的算法

voidMerge例題52,23,80,36,68,14(s=1,t=6)[52,23,80][36,68,14][52,23][80][52][23,52][23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]例題52,23,80,36,68,算法的效率時(shí)間復(fù)雜度方面，由于每趟歸并的時(shí)間復(fù)雜度O(n)，而對(duì)于有n個(gè)記錄的序列來說，一共需要進(jìn)行?log2n?趟歸并。因此歸并排序的時(shí)間復(fù)雜度是O(nlog2n)?？臻g復(fù)雜度方面，用順序表實(shí)現(xiàn)歸并排序時(shí)，需要和待排序記錄個(gè)數(shù)相等的輔助存儲(chǔ)空間，所以空間復(fù)雜度為O(n)。算法的效率時(shí)間復(fù)雜度方面，由于每趟歸并的時(shí)間復(fù)雜度O(n)，總結(jié)歸并排序很顯然是一種穩(wěn)定的排序方法。它也可用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的記錄序列，并且不需要輔助的記錄存儲(chǔ)空間，但遞歸實(shí)現(xiàn)時(shí)仍然需要開辟相應(yīng)的遞歸工作棧?？偨Y(jié)歸并排序很顯然是一種穩(wěn)定的排序方法。歸并排序歸并排序歸并排序“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。歸并排序“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新利用歸并的思想實(shí)現(xiàn)排序假設(shè)初始序列含有n個(gè)記錄，則可看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到?n/2?個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并，……，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止，這種排序方法稱為2-路歸并排序。利用歸并的思想實(shí)現(xiàn)排序假設(shè)初始序列含有n個(gè)記錄，則可看成是n例題初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]例題初始關(guān)鍵字：[49][38][65][97]算法思想2-路歸并排序?qū)[low..high]中的記錄歸并排序后放入T[low..high]中。當(dāng)序列長(zhǎng)度等于1時(shí)，遞歸結(jié)束，否則：（1）將當(dāng)前序列一分為二，求出分裂點(diǎn)mid=?(low+high)/2?;（2）對(duì)子序列R[low..mid]遞歸，進(jìn)行歸并排序，結(jié)果放入S[low..mid]中；算法思想2-路歸并排序?qū)[low..high]中的記錄歸并算法思想（3）對(duì)子序列R[mid+1..high]遞歸，進(jìn)行歸并排序，結(jié)果放入S[mid+1..high]中；（4）調(diào)用算法Merge，將有序的兩個(gè)子序列S[low..mid]和S[mid+1..high]歸并為一個(gè)有序的序列T[low..high]。算法思想（3）對(duì)子序列R[mid+1..high]遞歸，進(jìn)行算法描述voidMsort(RedTypeR[],RedType&T[],ints,intt){

//將R[s..t]歸并排序?yàn)門[s..t]if(s==t)T[s]=R[s];else{m=(s+t)/2;//將R[s..t]平分為R[s..m]和R[m+1..t]Msort(R,TR2,s,m);//遞歸地將R[s..m]歸并為有序的TR2[s..m]

Msort(R,TR2,m+1,t);//遞歸地R[m+1..t]歸并為有序的TR2[m+1..t]Merge(TR2,T,s,m,t);}//將TR2[s..m]和TR2[m+1..t]歸并到T[s..t]

}//Msort

算法描述voidMsort(RedTypeR[],算法描述

voidMergeSort(SqList&L){//對(duì)順序表L作2-路歸并排序

MSort(L.r,L.r,1,L.length);}//MergeSort算法描述

將兩個(gè)有序表歸并為一個(gè)新的有序表的算法

voidMerge(RedTypeR[],RedType&T[],inti,intm,intn){

//將有序的記錄序列R[i..m]和R[m+1..n]歸并為有序的記錄序列T[i..n]

intj,k;for(j=m+1,k=i;i<=m&&j<=n;++k){//將SR中記錄由小到大地并入TRifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)//TR[k..n]=SR[i..m];將剩余的SR[i..m]復(fù)制到TRwhile(k<=n&&i<=m)TR[k++]=SR[i++];if(j<=n)//將剩余的SR[j..n]復(fù)制到TRwhile(k<=n&&j<=n)TR[k++]=SR[j++];}//Merge將兩個(gè)有序表歸并為一個(gè)新的有序表的算法

voidMerge例題52,23,80,36,68,14(s=1,t=6)[52,23,80][36,68,14][52,23][80][52][23,52][23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]例題52,23,80,36,68,算法的效率時(shí)間復(fù)雜度方面，由于每趟歸并的時(shí)間復(fù)雜度O(n)，