數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--二路歸并排序說明書(編輯修改稿)
2025-07-09 14:51 本頁面
【文章內(nèi)容簡介】 TR2,s,m)。 /* 遞 歸 地 將 SR[s..m] 歸 并 為 有 序 的TR2[s..m] */ 11 MSort(SR,TR2,m+1,t)。 /* 遞 歸 地 將 SR[m+1..t] 歸 并 為 有 序TR2[m+1..t] */ 12 Merge(TR2,TR1,s,m,t)。 /* 將 TR2[s..m]和 TR2[m+1..t]歸并到TR1[s..t] */ 13 } 14 } 1) MSort 被調(diào)用時， SR 與 TR1 都是 {50,10,90,30,70,40,80,60,20}， s=1， t=9，最終我們的目的就是要將 TR1 中的數(shù)組排好順序。 2) 第 5 行，顯然 s 不等于 t，執(zhí)行第 8～ 13 行語句塊。 3) 第 9 行， m=(1+9)/2=5。 m就是序列的正中間下標 4) 此時第 10 行，調(diào)用 “MSort(SR,TR2,1,5)?！钡哪繕司褪菍?shù)組 SR 中的第 1～ 5的關(guān)鍵字歸并到有序的 TR2（調(diào)用前 TR2 為空數(shù)組），第 11 行，調(diào)用“MSort(SR,TR2,6,9)?！钡哪繕司褪菍?shù)組 SR 中的第 6～ 9 的關(guān)鍵字歸并到有序的 TR2。也就是說，在調(diào)用這兩句代碼之前，代碼已經(jīng)準備將數(shù)組分成兩組。如 圖 4 所示： 圖 4 5) 第 12 行，函數(shù) Merge 的代碼細節(jié)一會再講，調(diào)用 “Merge(TR2,TR1,1,5,9)。”的塔里木大學信息工程學院課程設(shè)計 5 / 11 目標其實就是將第 10 和 11 行代碼獲得的數(shù)組 TR2（注意它是下標為 1～ 5 和 6～ 9 的關(guān)鍵字分別有序）歸并為 TR1，此時相當于整 個排序就已經(jīng)完成了。如圖 5 所示： 圖 5 6) 第 10 行遞歸調(diào)用進去后， s=1， t=5， m=(1+5)/2=3。此時相當于將 5 個記錄再為三個和兩個。繼續(xù)遞歸進去，直到細分為一個記錄填入 TR2，此時 s 與 t 相等，遞歸返回，如圖 6 的左圖。每次遞歸返回后都會執(zhí)行當前遞歸函數(shù)的第 12 行，將 TR2 歸并到 TR1 中。如圖 6 的右圖。最終使得當前序列有序。 圖 6 7) 同樣的第 11 行也是類似方式，如圖 7。 圖 7 8) 此時也就是剛才所講的最后一次執(zhí)行第 12 行代碼，將 {10,30,50,70,90}與塔里木大學信息工程學院課程設(shè)計 6 / 11 {20,40,60,80}歸并為最終有序的序列。 以下是對此段遞歸算法程序的圖示： (如圖 8) 圖 8 歸并排序算法的整合 在經(jīng)過每個新的排序片段以后，程序產(chǎn)生新的數(shù)組，如何讓新的數(shù)組依然按照一定順序進行排序 , 即將 SR[i..m]和 SR[m+1..n]歸并為有序的 TR[i..n]，此時就要進行 Merge()函數(shù)的調(diào)用。一下就是 Merge()函數(shù)實現(xiàn)的詳細過程： /* 將有序的 SR[i..m]和 SR[m+1..n]歸并為有序的 TR[i..n] */ 1 void Merge(int SR[],int TR[],int i,int m,int n) 2 { 3 int j,k,l。 4 4 for(j=m+1,k=i。i=m amp。amp。 j=n。k++) /* 將 SR中記錄由小到大歸并入TR */ 5 { 6 if (SR[i]SR[j]) 7 TR[k]=SR[i++]。 8 else 9 9 TR[k]=SR[j++]。 10
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1