[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)第9章 排序 中國石油大學(xué)華東-文庫吧
2025-09-20 04:12 本頁面
【正文】 況下排序的時(shí)間復(fù)雜度為 o(n2)。 直接插入排序是一種 穩(wěn)定的 排序方法。 基本思想是 : 設(shè)在順序表中有一 個(gè)元素序列 V[0], V[1], …, V[ n1]。其中 , V[0], V[1], …, V[ i1] 是已經(jīng)排好序的元素。 1)在插入 V[i] 時(shí) , 利用折半搜索法尋找 V[i] 的插入位置。 2)找到位置后，再將插入位置之后的元素向后順次移動(dòng)。 3)插入。 折半插入排序 (Binary Insertsort) 10 算法分析 折半搜索比順序搜索快 , 所以折半插入排序 就 平均性能來說比直接插入排序要快。 它所需的 排序碼比較次數(shù)與待排序元素序列的初始排列無關(guān) ，僅依賴于元素個(gè)數(shù)。 折半插入排序是一個(gè) 穩(wěn)定的 排序方法。 11 ? 希爾排序 方法又稱為 縮小增量排序， 基本思想是 : 1） 選擇一個(gè)步長序列 d1， d2， … ， dk，其中 didj (ij), dk=1； 2）按步長序列個(gè)數(shù) k，對序列進(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è)序列 分別對各序列進(jìn)行直接插入排序。 4）重復(fù)上述步驟，僅步長因子為 1時(shí)，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度。 希爾排序 (Shell Sort) 取 d3=1 三趟分組： 13 27 48 55 4 49 38 65 97 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)定 的排序方法。 Gap的取法有多種。最初 shell 提出取 gap = ?n/2?，gap = ?gap/2?，直到 gap = 1。 knuth 提出取 gap = ?gap/3? +1。還有人提出都取奇數(shù)為好，也有人提出各 gap 互質(zhì)為好。 想要弄清排序碼比較次數(shù)和元素移動(dòng)次數(shù)與增量選擇之間的依賴關(guān)系 ， 并給出完整的數(shù)學(xué)分析 ， 還沒有人能夠做到 。 14 交換排序 ( Exchange Sort ) 基本思想是兩兩比較待排序元素的排序碼，如果發(fā)生逆序，則交換之。直到所有元素都排好序?yàn)橹埂? 思想：小的浮起，大的沉底。從左端開始比較。 第一趟：第 1個(gè)與第 2個(gè)比較，大則交換；第 2個(gè)與第 3個(gè)比較，大則交換， …… 關(guān)鍵字最大的記錄交換到最后一個(gè)位置上； 第二趟：對前 n1個(gè)記錄進(jìn)行同樣的操作，關(guān)鍵字次大的記錄交換 到第 n1個(gè)位置上； 依次
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1