[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)第9章排序中國(guó)石油大學(xué)華東-文庫吧資料
2024-10-25 04:12本頁面
【正文】 76 三趟排序： 4 13 27 38 48 49 55 65 76 97 例 初始： 49 38 65 97 76 13 27 48 55 4 一趟排序： 13 27 48 55 4 49 38 65 97 76 二趟排序： 13 4 48 38 27 49 55 65 97 76 取 d1=5 一趟分組： 49 38 65 97 76 13 27 48 55 4 取 d2=3 二趟分組： 13 27 48 55 4 49 38 65 97 76 13 算法分析： 希爾排序是一種 不穩(wěn)定 的排序方法。 11 ? 希爾排序 方法又稱為 縮小增量排序， 基本思想是 : 1） 選擇一個(gè)步長(zhǎng)序列 d1， d2， … ， dk，其中 didj (ij), dk=1； 2）按步長(zhǎng)序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k趟排序； 3）第 I趟排序時(shí)， 從第一個(gè)關(guān)鍵字開始，將間隔為 di的關(guān)鍵字組成一個(gè)序列； 從第二個(gè)關(guān)鍵字開始，將間隔為 di的關(guān)鍵字組成一個(gè)序列； …………………………………………………… 從第 di個(gè)關(guān)鍵字開始，將間隔為 di的關(guān)鍵字組成一個(gè)序列 分別對(duì)各序列進(jìn)行直接插入排序。 它所需的 排序碼比較次數(shù)與待排序元素序列的初始排列無關(guān) ，僅依賴于元素個(gè)數(shù)。 3)插入。 1)在插入 V[i] 時(shí) , 利用折半搜索法尋找 V[i] 的插入位置。 基本思想是 : 設(shè)在順序表中有一 個(gè)元素序列 V[0], V[1], …, V[ n1]。 21 25 49 28 16 08 0 1 2 3 4 5 9 平均情況下排序的時(shí)間復(fù)雜度為 o(n2)。 最好情況下，排序前元素已按排序碼從小到大有序，每趟只需與前面有序元素序列的最后一個(gè)元素比較 1次，總的排序碼比較次數(shù)為 n1, 元素移動(dòng)次數(shù)為 0。 直接插入排序 (Insert Sort) 5 各趟排序結(jié)果 21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 08 25 i = 1 0 1 2 3 4 5 temp 21 25 49 25* 16 08 49 i = 2 6 0 1 2 3 4 5 i = 4 i = 5 i = 3 0 1 2 3 4 5 temp 21 25 49 25* 16 08 16 0 1 2 3 4 5 temp 21 25 49 25* 16 08 25* 0 1 2 3 4 5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1