[計算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)第9章排序中國石油大學(xué)華東-免費(fèi)閱讀
【正文】 通常需考慮的因素有：待排序的記錄個數(shù)；記錄本身的大??；記錄的鍵值分布情況等。如此反復(fù)，便得到一個按關(guān)鍵字有序的序列。jn。 快速排序 (Quick Sort) 做法： 附設(shè)兩個指針 low和 high ，初值分別指向 第一個記錄和 最后一個記錄 ，設(shè) 支點(diǎn)記錄 為 r[1] ， (r[1]通常取第一個記錄的值為基準(zhǔn)值。 想要弄清排序碼比較次數(shù)和元素移動次數(shù)與增量選擇之間的依賴關(guān)系 ， 并給出完整的數(shù)學(xué)分析 ， 還沒有人能夠做到 。 折半插入排序是一個 穩(wěn)定的 排序方法。 直接插入排序是一種 穩(wěn)定的 排序方法。 4 插入排序 (Insert Sorting) 基本方法是 ：每步將一個待排序的元素，按其排序碼大小，插入到前面已經(jīng)排好序的一組元素的適當(dāng)位置上 , 直到元素全部插入為止。 基本思想是 : 當(dāng)插入第 i (i≥ 1) 個元素時，前面的 V[0], V[1], …, V[ i1]已經(jīng)排好序。 基本思想是 : 設(shè)在順序表中有一 個元素序列 V[0], V[1], …, V[ n1]。 11 ? 希爾排序 方法又稱為 縮小增量排序， 基本思想是 : 1） 選擇一個步長序列 d1， d2， … ， dk，其中 didj (ij), dk=1； 2）按步長序列個數(shù) k，對序列進(jìn)行 k趟排序； 3）第 I趟排序時， 從第一個關(guān)鍵字開始，將間隔為 di的關(guān)鍵字組成一個序列； 從第二個關(guān)鍵字開始，將間隔為 di的關(guān)鍵字組成一個序列； …………………………………………………… 從第 di個關(guān)鍵字開始，將間隔為 di的關(guān)鍵字組成一個序列 分別對各序列進(jìn)行直接插入排序。 14 交換排序 ( Exchange Sort ) 基本思想是兩兩比較待排序元素的排序碼，如果發(fā)生逆序，則交換之。 ) 首先從 high所指位置起 向前 搜索，找到第一個 小于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換（大的原地不動）， 然后從 low 所指位置起 向后 搜索，找到第一個 大于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換（小的原地不動）， 重復(fù)這兩步直至 low=high為止。++j) if ( L[j].keyL[k].key) k=j。稱這個過程為堆排序。 在最好情況下，直接插入排序和冒泡排序最快； 在平均情況下，快速排序最快； 在最壞情況下，堆排序和歸并排序最快。 初始序列： 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)缺點(diǎn)，故在不同情況下可作不同的選擇。然后，再對剩下的 n1個元素建成堆，輸出堆頂元素，得到 n個元素中關(guān)鍵字次小 (或次大 )的元素。++i） { k=i； 第 I小的元素 for(j=i+1。 ③ 然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的元素都排在相應(yīng)位置上為止。還有人提出都取奇數(shù)為好，也有人提出各 gap 互質(zhì)為好。 它所需的 排序碼比較次數(shù)與待排序元素序列
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1