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

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

//將R[s..t]歸并排序為T[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){//對順序表L作2-路歸并排序

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

將兩個有序表歸并為一個新的有序表的算法

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將兩個有序表歸并為一個新的有序表的算法

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

//將R[s..t]歸并排序為T[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){//對順序表L作2-路歸并排序

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

將兩個有序表歸并為一個新的有序表的算法

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將兩個有序表歸并為一個新的有序表的算法

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,算法的效率時間復(fù)雜度方面，由于每趟歸并的時間復(fù)雜度O(n)，