數(shù)據(jù)結(jié)構(gòu)第25講-歸并排序和數(shù)排序-C.ppt

《數(shù)據(jù)結(jié)構(gòu)第25講-歸并排序和數(shù)排序-C.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第10章內(nèi)部排序10.1排序的基本概念10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法的比較10.5歸并排序歸并就是將兩個或兩個以上的有序數(shù)據(jù)序列合并成一個有序數(shù)據(jù)序列的過程。采用歸并的思想進行排序—歸并排序。假設初始序列含有n個記錄，則可看成是n個有序的子序列；每個子序列的長度為1，然后兩兩歸并，得到?n/2?個長度為2或1有序的子序列，再兩兩歸并，...如此重復，直至得到一個長度為n的有序序列為止。這種排序方法稱為2-路歸并。例：關(guān)鍵字序列T=（21，25，49，25*，93，62，72

2、，08，37，16，54），請給出歸并排序的具體實現(xiàn)過程。212525*9362720837165449212525*4962930872163754163754212525*490862729308212525*496272930816212525*374954627293len=1len=2len=4len=8len=16163754整個歸并排序僅需?log2n?趟voidMerge(RcdTypeSR[]，RcdType&TR[]，inti，intm，intn){//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n

3、]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]復制到TRif(j<=n)TR[k..n]=SR[j..n];//將剩余的SR[j..n]復制到TR}//merge2-路歸并排序的核心操作是將一維數(shù)組中前后相鄰的兩個有序序列歸并為一個有序序列，其算法為：一趟歸并排序的操作是，調(diào)用[n/2h]次算法merge將

4、SR[1..n]中前后相鄰且長度為h的有序段進行兩兩歸并，得到前后相鄰、長度為2h的有序段，并存放在TR[1..n]中，整個歸并排序需進行[log2n]趟。voidMSort(RcdTypeSR[]，RcdType&TR1[]，ints，intt){//將SR[s..t]歸并排序為TR1[s..t]if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//將SR[s..t]平分為SR[s..m]SR[m+1..t]Msort(SR,TR2,s,m)//遞歸地將SR[s..m]歸并為TR2[s..m]Msort(SR,TR2,m

5、+1,t)//遞歸地將SR[m+1..t]歸并為TR2[m+1..t]Merge(TR2,TR1,s,m,t)//TR2[s..m]和TR2[m+1..t]歸并為TR1[s..t]}}//Msort遞歸形式的2-路歸并排序算法：voidMergeSort(SqList&L){//對順序表L進行歸并排序Msort(L.r，L.r，1，L.length)}//MergeSort歸并排序分析在歸并排序算法中，遞歸深度為O(log2n)，記錄關(guān)鍵字的比較次數(shù)為O(nlog2n)。算法總的時間復雜度為O(nlog2n)。歸并排序占用附加存儲較多，需要另外

6、一個與原待排序記錄數(shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。與快速排序和堆排序相比，歸并排序的最大特點是，它是一種穩(wěn)定的排序方法。第10章內(nèi)部排序10.1排序的基本概念10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法的比較10.6基數(shù)排序1.多關(guān)鍵字排序以撲克牌排序為例。每張撲克牌有兩個“關(guān)鍵字”：花色和面值。其有序關(guān)系為：花色：???????面值：2<3<4<5<6<7<8<9<10

7、,?A這就是多關(guān)鍵字排序。排序后形成的有序序列叫做詞典有序序列。對于上例兩關(guān)鍵字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情況下，假定有一個n個對象的序列{R1,R2,…,Rn}，且每個對象Ri中含d個關(guān)鍵字如果對序列中任意兩個對象Ri和Rj(1≤i

8、nificantDigitfirst)最低位優(yōu)先LSD(LeastSignificantDigitfirst)1）最高位優(yōu)先法通常是一個