[計算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)第9章排序中國石油大學(xué)華東(參考版)
2024-10-22 04:12本頁面
【正文】 。 在最好情況下，直接插入排序和冒泡排序最快； 在平均情況下，快速排序最快； 在最壞情況下，堆排序和歸并排序最快。 初始序列： 39,80,76,41,13, 29,50,78,30,11,100, 7 第一趟： [39,80],[41,76],[13,29],[50,78],[11,30],[7,100] 第二趟： [39,41,76,80], [13,29,50,78], [7,11,30,100] 第三趟： [13,29,39,41,50,76,78,80], [7,11,30,100] 第四趟： [7, 11, 13, 29, 30, 39, 41, 50, 76, 78, 80, 100] 33 34 各種排序方法的比較 各種排序方法各有優(yōu)缺點，故在不同情況下可作不同的選擇。其基本思想是： 設(shè)初始元素序列有 n 個元素，首先把它看成是 n 個 長度為 1 的有序子序列（歸并項），做兩兩歸并，得到 ?n/2? 個 長度為 2 的歸并項（最后一個歸并項的長度為 1）； 再做兩兩歸并，得到 ?n/4? 個 長度為 4 的歸并項（最后一個歸并項長度可以短些） … ，如此重復(fù)，最后得到一個長度為 n 的有序序列。 把具有 n個記錄的表看成是 n個有序的子表，每個子表的長度為 1，然后兩兩歸并，得到 [n/2]個長度為 2或為 1的有序子表；再兩兩歸并，如此重復(fù)，直到得到一個長度為 n的有序表為止。稱這個過程為堆排序。然后，再對剩下的 n1個元素建成堆，輸出堆頂元素，得到 n個元素中關(guān)鍵字次小 (或次大 )的元素。 89 76 24 33 15 10 11 25 36 49 78 56 23 堆排序 (Heap Sort) 堆排序思想：設(shè)有 n個元素，將其按關(guān)鍵字排序。 L[i]=L[k]。++j) if ( L[j].keyL[k].key) k=j。++i） { k=i； 第 I小的元素 for(j=i+1。 21 直接選擇排序 (Select Sort) 直接選擇排序的算法如下： void SelectSort( STBL L[ ],int n) { int i,j,k,t。然后再從第 2 個到第 n個元素中選出次小的記錄交換到 第二個 位置上，依次類推。 ) 首先從 high所指位置起 向前 搜索，找到第一個 小于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換（大的原地不動）， 然后從 low 所指位置起 向后 搜索，找到第一個 大于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換（小的原地不動）， 重復(fù)這兩步直至 low=high為止。 ③ 然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的元素都排在相應(yīng)位置上為止。 第一趟：第 1個與第 2個比較，大則交換；第 2個與第 3個比較，大則交換， …… 關(guān)鍵字最大的記錄交換到最后一個位置上； 第二趟：對前 n1個記錄進(jìn)行同樣的操作，關(guān)鍵字次大的記錄交換 到第 n1個位置上； 依次類推，則完成排序。 思想：小的浮起，大的沉底。 14 交換排序 ( Exchange Sort ) 基本思想是兩兩比較待排序元素的排序碼，如果發(fā)生逆序，則交換之。還有人提出都取奇數(shù)為好，也有人提出各 gap 互質(zhì)為好。最初 shell 提出取 gap = ?n/2?，gap = ?gap/2?，直到 gap = 1。 希爾排序 (Shell Sort) 取 d3=1 三趟分組： 13 27 48 55 4 49 38 65 97
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1