[理學(xué)]大學(xué)教程零起點數(shù)據(jù)結(jié)構(gòu)--排序(參考版)
2024-12-11 00:50本頁面
【正文】 ４．對每個關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。 64 分配排序 箱（桶）排序 { 78, 17, 39, 26, 72, 94, 21, 12， 23, 68 } B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9] 26 39 94 78 21 72 17 桶 010 2030 4050 6070 8090 12 23 68 每個桶首尾相連，收集即可得到有序序列 65 基數(shù)排序是一種借助 “多關(guān)鍵字排序”的思想來實現(xiàn) “單關(guān)鍵字排序”的內(nèi)部排序算法。 已知一組鍵值序列 （ 13， 12， 16， 17， 15， 14， 11）， 試采用二路歸并排序法對該組序列作升序排序 并給出每一趟的排序結(jié)果 已知一組鍵值序列 (26， 21， 32， 56， 78， 89， 90)， 試采用二路歸并排序法對該組序列 作升序排序， 并給出每一趟的排序結(jié)果。 k++。 } while( jbn ) { c[k]=b[j]。 i++。 k++。 } else { c[k]=a[j]。 i++。amp。 k=1。 56 歸并排序 基本思想： 將多個有序序列合并成一個有序序列 將兩個有序子序列合并為一個有序序列 稱為 2路歸并排序 將具有 n個記錄的序列看成是 n個長度為 1的有序序列 然后進行兩兩歸并， 得到多個長度為 2的有序序列，繼續(xù)兩兩歸并， 如此重復(fù)，直至得到一個長度為 n的有序序列為止 57 寫出鍵值 83， 40， 63， 13， 84， 35， 96， 57， 39， 79， 61， 15 應(yīng)用二路歸并排序算法從小到大排序后各趟的結(jié)果。 55 設(shè)要將序列 （ Q， H， C， Y， P， A， M， S， R）按字母升序排序， 請分別畫出采用堆排序方法時建立的初始堆， 以及第一次輸出堆頂元素后經(jīng)過篩選調(diào)整的堆形態(tài)。 例如： ( 36,14,18,80,75,6,46 ) 36 14 18 80 75 6 46 6 18 366 3651 已知一組鍵值序列 （ 32， 44， 38， 65， 53， 42， 29， 57）， 試采用堆排序法對該組序列作升序排序， 給出建立的初始堆 以及第一次輸出堆元素后篩選調(diào)整的堆 32 44 38 65 53 42 29 57 52 已知一組鍵值序列 （ 32， 44， 38， 65， 53， 42， 29， 57）， 試采用堆排序法對該組序列作升序排序， 給出建立的初始堆 以及第一次輸出堆元素后篩選調(diào)整的堆 32 44 38 65 53 42 29 57 57652938293253 已知一組鍵值序列 （ 32， 44， 38， 65， 53， 42， 29， 57）， 試采用堆排序法對該組序列作升序排序， 給出建立的初始堆 以及第一次輸出堆元素后篩選調(diào)整的堆 32 44 38 65 53 42 29 57 57652938293229 65656554 已知一組鍵值序列 （ 33， 37， 26， 43， 55， 67， 42， 38）， 試采用堆排序法對該組序列作升序排序， 給出建立的初始堆， 以及第一次輸出堆元素后篩選調(diào)整的堆。 50 (2) 初建堆：給定序列建立堆 先取 i=n/2，將以 i結(jié)點為根的子樹調(diào)整成為堆，然后令 i=i1；再將以 i結(jié)點為根的子樹調(diào)整成為堆。 46 46146 14 49 80 75 6 36 18 46 46 146 14 36183618 757536 808046 (1) 輸出堆頂元素，調(diào)整堆 調(diào)整方法為： n個結(jié)點的堆，輸出堆頂，剩 n1個結(jié)點將堆尾結(jié)點送入堆頂，堆可能被破壞，將根結(jié)點與左、右孩子中較小的進行交換。 兩個問題： 1，輸出堆頂后，如何調(diào)整堆 2，如何建立一個堆 48 14 80 75 46 18 6 3618 (1) 輸出堆頂元素，調(diào)整堆 調(diào)整方法為： n個結(jié)點的堆，輸出堆頂，剩 n1個結(jié)點將堆尾結(jié)點送入堆頂，堆可能被破壞，將根結(jié)點與左、右孩子中較小的進行交換。 輸出 “ 冠軍 ” 后 ， 將 （ 冠軍 ） 葉子結(jié)點關(guān)鍵字改為最大 ， 繼續(xù)進行錦標(biāo)賽排序 ， 直到選出關(guān)鍵字次小的記錄為止 ， 如此循環(huán)直到輸出全部有序序列 。 } } 時間復(fù)雜度： O（ n2） 直接選擇排序是不穩(wěn)定的 41 選擇排序 基本思想：對 n個待排序記錄的關(guān)鍵字進行兩兩比較 ，從中選出 n/2個較小者再兩兩比較 ， 直到選出關(guān)鍵字最小的記錄為止 ， 此為一趟排序 。 j++ ) if( r[j].key r[k].key ) k=j。 for( j=i+1。 i=n1。 } } r[i]=r[0] quick ( r,low,i1 )。 if( ij ) { r[j]=r[i]。amp。 i++。 r[j].key=r[0].key ) j。 while( ij ) { while( ij amp。 503， 87， 512， 61， 908， 170， 897， 275， 653， 462 503 i j 503 87 512 61 908 170 897 275 653 462 462 512275 908170 503 第一趟排序結(jié)果 33 34 35 low到 high之間記錄進行快速排序 Void quick （ list r， int low， int high） { i=low； j=high； r[0]=r[i]。然后對這兩部分記錄繼續(xù)快速排序，以達(dá)到整個序列按關(guān)鍵字有序。 12. } 13. } 14. } 15. } 重復(fù)上述過程，直到“ 在一趟排序過程中沒有進行過交換記錄的操作 ”為止 28 快速排序 又稱劃分交換排序，交換排序的一種 基本思想 任取一個記錄為基準(zhǔn)，通過比較關(guān)鍵字、交換記錄，將待排序列分成兩組。 ++j
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1