數(shù)據(jù)結(jié)構(gòu)課件第十章-文庫吧
2025-04-23 00:10 本頁面
【正文】 [ 15 27 36 53 69 ] 42 ?low ? high ?mid [ 15 27 36 53 69 ] 42 [ 15 27 36 42 53 69 ] ( 4236 ) ( 4253 ) 15 3）希爾（ shell）排序 （又稱縮小增量排序 ） 基本思想 ：先將整個待排記錄序列分割成若干子序列 ,分別進(jìn)行直接插入排序，待整個序列中的記錄 “ 基本有序 ”時，再對全體記錄進(jìn)行一次直接插入排序。 技巧： 子序列的構(gòu)成不是簡單地 “ 逐段分割 ” ，而是將相隔某個增量 dk的記錄組成一個子序列 ,讓增量 dk逐趟縮短（例如依次取 5,3,1），直到 dk＝ 1為止。 優(yōu)點(diǎn)： 讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。 16 ?例 對下列序列采用希爾排序 49 38 65 97 76 13 27 49 55 04 第一趟希爾排序 增量為 5 49 38 65 97 76 13 27 49 55 04 13 49 27 38 49 65 97 55 04 76 17 ?例 對下列序列采用希爾排序 49 38 65 97 76 13 27 49 55 04 第二趟希爾排序 增量為 3 13 49 27 38 49 65 97 55 04 76 13 38 55 76 04 27 65 49 49 97 18 ?例 對下列序列采用希爾排序 49 38 65 97 76 13 27 49 55 04 第三趟希爾排序 增量為 1 13 38 55 04 27 65 49 49 97 76 04 13 27 38 49 49 55 65 76 97 19 ? 時間性能 ： 希爾排序的分析非常困難，原因是何種步長序列最優(yōu)難以斷定。通常認(rèn)為時間復(fù)雜度為： O(n3/2)。 較好的步長序列： …… 121 、 1 1。 可由遞推公式 Si= 3Si1 + 1 產(chǎn)生。 ? 空間性能 ：只用一個額外空間，空間復(fù)雜度為O(1)； ? 穩(wěn)定性 ：希爾排序是不穩(wěn)定的排序算法 ?效率分析 20 交換排序 兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹埂? 交換排序的主要算法有： 1) 冒泡排序 2) 快速排序 交換排序的基本思想是： 21 1) 冒泡排序 基本思路： 每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。 優(yōu)點(diǎn)： 每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。 前提： 順序存儲結(jié)構(gòu) 例： 關(guān)鍵字序列 T=(21， 25， 49， 25*， 16， 08），請寫出冒泡排序的具體實(shí)現(xiàn)過程。 21， 25， 49， 25*， 16， 08 21， 25， 25*， 16， 08 ， 49 21， 25， 16， 08 ， 25*， 49 21， 16， 08 ， 25， 25*， 49 16， 08 ， 21， 25， 25*， 49 08， 16， 21， 25， 25*， 49 初態(tài)： 第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 22 2） 快速排序 從待排序列中任取一個元素 (例如取第一個 ) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個。此時便為有序序列了。 基本思想： 優(yōu)點(diǎn)： 因?yàn)槊刻丝梢源_定不止一個元素的位置，而且呈指數(shù)增加，所以特別快！ 前提： 順序存儲結(jié)構(gòu) 23 快速排序舉例 初始關(guān)鍵字： {49， 38， 65， 97， 76， 13， 27， 49} pivot key 49 j j i 1次交換后： {27， 38， 65， 97， 76， 13， ， 49} i j i 2次交換后： {27， 38， ， 97， 76， 13， 65， 49} i j j 3次交換后： {27， 38， 13， 97， 76， ， 65， 49} i j i 4次交換后： {27， 38， 13， ， 76， 97， 65， 49} j i j 一趟完成后： {27， 38， 13， 49， 76， 97， 65， 49} 24 ?例 對下列序列采用快速排序 49 38 65 97 76 13 27 49 第 趟快速排序 1 49 38 65 97 76 13 27 49 樞軸 low high 49 low high low high high low==high則此位置就是樞軸 49的最終位置 第一趟快速排序結(jié)束 25 ?例 對下列序列采用快速排序 49 38 65 97 76 13 27 49 第 趟快速排序 1 227 38 13 49 76 97 65 49 樞軸 首先對 49之前的數(shù)據(jù)采用快速排序 27 low high low==high 27樞軸 27之前和之后都只有一個值，不再需要排序 13 3826 ?例 對下列序列采用快速排序 49 38 65 97 76 13 27 49 第 趟快速排序 2 然后對 49之后的數(shù)據(jù)采用快速排序 13 38 49 76 97 65 49 樞軸 76 low high low Low==high 76樞軸 76后面的 97也不需再次排序 27 97第二趟快速排序結(jié)束 27 ?例 對下列序列采用快速排序 49 38 65 97 76 13 27 49 第 趟快速排序 2 313 38 49 4
研究報告相關(guān)推薦
鄂ICP備17016276號-1