數(shù)據(jù)結(jié)構(gòu)查找與排序ppt課件

1、第一部分 查找二分查找,Hash表 二分查找考點(diǎn)二分查找考點(diǎn) 條件：順序存儲(chǔ)條件：順序存儲(chǔ),按關(guān)鍵字有序按關(guān)鍵字有序 時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度分析log2n） 最多要比較的次數(shù)（最多要比較的次數(shù)（2n +1 ）,理由：理由：n個(gè)結(jié)點(diǎn)的判個(gè)結(jié)點(diǎn)的判定樹(shù)的深度與定樹(shù)的深度與n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度相同。個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度相同。 折半查找的二叉判定樹(shù)折半查找的二叉判定樹(shù)1、請(qǐng)問(wèn),滿足什么條件的順序表可以實(shí)施二分查找,在滿足該條件的n個(gè)記錄的順序表中進(jìn)行二分查找,最大的比較次數(shù)是多少？答：數(shù)據(jù)元素初始狀態(tài)按關(guān)鍵字有序 最大比較次數(shù)應(yīng)為2n +12、設(shè)順序表為4, 6, 12, 38, 40, 67

2、, 80用二分法查找72,需要進(jìn)行的比較次數(shù)為（ ）A、3 B、n-1 C、n+1 D、n 答案：A 例如：3、試用于折半查找的表的存儲(chǔ)方式及元素排列要求是順序存儲(chǔ)、試用于折半查找的表的存儲(chǔ)方式及元素排列要求是順序存儲(chǔ),按關(guān)鍵字有序。按關(guān)鍵字有序。4、對(duì)有10個(gè)元素的有序表,采用二分查找,需要比較4次方可找到的元素個(gè)數(shù)為 3 。5、設(shè)有序順序表中的元素依次為017,094,154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908.試畫(huà)出對(duì)其進(jìn)行折半搜索時(shí)的判定樹(shù),并計(jì)算搜索成功的平均搜索長(zhǎng)度。 Hash查找和Hash表的創(chuàng)建 常用Ha

3、sh函數(shù)和解決沖突方法 Hash表的創(chuàng)建與平均查找長(zhǎng)度的計(jì)算 時(shí)間復(fù)雜度的分析不依賴問(wèn)題的規(guī)模,與解決沖突的方法以及hash表的裝填因子有關(guān)）例如例如1、對(duì)包含N個(gè)元素的散列表進(jìn)行檢索,平均檢索長(zhǎng)度是（ ）A、O(log2N) B、O(N)C、不直接依賴于N D、上述三者都不是 答案：C2、已知待散列存儲(chǔ)的關(guān)鍵字序列為4,15,38,49,33,60,27,71）,哈希函數(shù)為Hkey）=keyMOD11,哈希表HT的長(zhǎng)度為11,采用二次探測(cè)再散列法d=12,-12,22,-22,32,）解決沖突,試構(gòu)造此哈希表,并求出在等概率情況下查找成功的平均查找長(zhǎng)度。位置012345678910關(guān)鍵字33

4、6027415387149沖突次數(shù)04501163查找時(shí)比較次數(shù)15612274查找成功的平均查找長(zhǎng)度=（1+5+6+1+2+2+7+4）/8=28/8=3.53、已知關(guān)鍵碼集合53,17,19,61,98,75,79,63,46,49要求散列到地址區(qū)間100, 101, 102, 103, 104, 105, 106,107,108,109內(nèi),若發(fā)生沖突則用開(kāi)地址法的線索探測(cè)法解決,要求寫(xiě)出的選用的散列函數(shù),形成的散列表：計(jì)算查找成功的平均搜索長(zhǎng)度。（設(shè)等概率情況）答：選用的散列函數(shù)為：H(K)=100 + K%10位置100101102103104105106107108109關(guān)鍵字796

5、14953637546179819沖突次數(shù)1030100000查找時(shí)比較次數(shù)2141211111查找成功時(shí)的平均搜索長(zhǎng)度：（2 + 1 + 4 + 1+ 2 + 1 + 1 + 1 + 1 + 1）/10=1.5第二部分 排序 各種排序算法的特性 時(shí)間性能最好、最壞、平均情況） 空間復(fù)雜度 穩(wěn)定性 常見(jiàn)排序算法 堆排序-堆的定義,創(chuàng)建堆,堆排序廈大3次,南航2次,南大3次） 快速排序 基數(shù)排序 插入排序 希爾排序 冒泡排序 簡(jiǎn)單選擇排序 歸并排序一、基于選擇的排序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序堆排序堆排序Heap Sort）算法關(guān)鍵部分：算法關(guān)鍵部分： for (i=1; i N; i+) min

6、= i ; for (j=i+1; j=N; j+) if (Aj314431353135 “挑選挑選”：除了堆頂元素之外：除了堆頂元素之外,其余元素都滿足堆的性質(zhì)其余元素都滿足堆的性質(zhì),把這樣一個(gè)數(shù)據(jù)集合把這樣一個(gè)數(shù)據(jù)集合做成一個(gè)堆做成一個(gè)堆,這個(gè)過(guò)程叫做這個(gè)過(guò)程叫做“挑選挑選” 。 挑選：實(shí)際上是一個(gè)尋找的過(guò)程挑選：實(shí)際上是一個(gè)尋找的過(guò)程,由于堆頂元素是唯一一個(gè)不滿足堆性質(zhì)的元由于堆頂元素是唯一一個(gè)不滿足堆性質(zhì)的元素素,則下面需要在下面的各個(gè)位置中則下面需要在下面的各個(gè)位置中,尋找它該處于的位置尋找它該處于的位置 首先比較該堆頂元素與其兩個(gè)孩子的大小首先比較該堆頂元素與其兩個(gè)孩子的大小,取

7、兩個(gè)孩子中較大的一個(gè)取兩個(gè)孩子中較大的一個(gè),若比該元若比該元素大素大,則把這個(gè)孩子提升一個(gè)層次則把這個(gè)孩子提升一個(gè)層次,再繼續(xù)比較原堆頂元素與這個(gè)孩子原來(lái)的再繼續(xù)比較原堆頂元素與這個(gè)孩子原來(lái)的孩子孩子,直到發(fā)現(xiàn)某個(gè)層次上直到發(fā)現(xiàn)某個(gè)層次上,原來(lái)元素的兩個(gè)孩子均不大于小于或等于原原來(lái)元素的兩個(gè)孩子均不大于小于或等于原堆頂元素堆頂元素,或者到了某個(gè)葉子結(jié)點(diǎn)位置上為止。或者到了某個(gè)葉子結(jié)點(diǎn)位置上為止。 問(wèn)題問(wèn)題1：挑選：挑選 問(wèn)題問(wèn)題2：堆的創(chuàng)建：堆的創(chuàng)建 依托依托“挑選的過(guò)程挑選的過(guò)程 “創(chuàng)建堆是指如何將已經(jīng)存在的創(chuàng)建堆是指如何將已經(jīng)存在的N個(gè)元素按堆最大堆個(gè)元素按堆最大堆或最小堆的要求存放在一個(gè)

8、一維數(shù)組中?；蜃钚《训囊蟠娣旁谝粋€(gè)一維數(shù)組中。 在線性時(shí)間復(fù)雜度下創(chuàng)建堆。具體分兩步進(jìn)行：在線性時(shí)間復(fù)雜度下創(chuàng)建堆。具體分兩步進(jìn)行：第一步第一步,將將N個(gè)元素按輸入順序存入二叉樹(shù)中個(gè)元素按輸入順序存入二叉樹(shù)中,這一步只要求滿這一步只要求滿足完全二叉樹(shù)的結(jié)構(gòu)特性足完全二叉樹(shù)的結(jié)構(gòu)特性,而不管其有序性。而不管其有序性。第二步第二步,按照完全二叉樹(shù)的層次遍歷的反序按照完全二叉樹(shù)的層次遍歷的反序,找到第一個(gè)非葉子結(jié)點(diǎn)找到第一個(gè)非葉子結(jié)點(diǎn),從該結(jié)點(diǎn)開(kāi)始從該結(jié)點(diǎn)開(kāi)始“挑選挑選”,調(diào)整各結(jié)點(diǎn)元素調(diào)整各結(jié)點(diǎn)元素,然后按照反序然后按照反序,依次做篩選依次做篩選,直到做完根結(jié)點(diǎn)元素直到做完根結(jié)點(diǎn)元素,此時(shí)即構(gòu)成

9、一個(gè)堆。此時(shí)即構(gòu)成一個(gè)堆。 時(shí)間復(fù)雜性時(shí)間復(fù)雜性 T(n) = Onlogn）,與數(shù)據(jù)初始狀態(tài)無(wú)關(guān)與數(shù)據(jù)初始狀態(tài)無(wú)關(guān),堆排序的堆排序的最佳、最差以及平均時(shí)間復(fù)雜度均為最佳、最差以及平均時(shí)間復(fù)雜度均為O(nlog2n) 空空 間復(fù)雜性間復(fù)雜性S(n) = O1） 穩(wěn)定性：不穩(wěn)定。因?yàn)槭翘S式的比較與交換。反例如下：穩(wěn)定性：不穩(wěn)定。因?yàn)槭翘S式的比較與交換。反例如下：不穩(wěn)定！不穩(wěn)定！排序前排序前2 領(lǐng)先于領(lǐng)先于 22 落后于落后于 2排序后排序后 堆排序特性屬于選擇排序大類）堆排序特性屬于選擇排序大類） 2 1 2 1 2 2 211223211223121223 適用場(chǎng)合：數(shù)據(jù)量比較大的情況適用

10、場(chǎng)合：數(shù)據(jù)量比較大的情況,因?yàn)槌跏紭?gòu)建堆所需比較次數(shù)較多。因?yàn)槌跏紭?gòu)建堆所需比較次數(shù)較多。設(shè)關(guān)鍵字序列為：49, 38, 66, 90, 75, 10, 20。請(qǐng)把這些關(guān)鍵字調(diào)整成堆頂元素取最小值的堆。（畫(huà)出過(guò)程）493890751066204938907566102010389075662049例如：例如：2序列是堆的是( C )。 A75, 65, 30, 15, 25, 45, 20, 10 B75, 65, 45, 10, 30, 25, 20, 15 C75, 45, 65, 30, 15, 25, 20, 10 D75, 45, 65, 10, 25, 30, 20, 153、對(duì)關(guān)

11、鍵碼序列45,30,55,21,94,66,90,82用堆排序方法進(jìn)行逆序排序,請(qǐng)畫(huà)出建立的初始堆以及調(diào)整3個(gè)關(guān)鍵碼的示意圖。三、基于交換的排序三、基于交換的排序冒泡排序冒泡排序Bubble Sort）快速排序快速排序Quick Sort） 1.冒泡排序冒泡排序Bubble Sort算法思想算法思想依次比較相鄰的兩個(gè)記錄的關(guān)鍵字依次比較相鄰的兩個(gè)記錄的關(guān)鍵字,若兩個(gè)記錄是反序的若兩個(gè)記錄是反序的(即前一個(gè)記錄的關(guān)即前一個(gè)記錄的關(guān)鍵字大于后前一個(gè)記錄的關(guān)鍵字鍵字大于后前一個(gè)記錄的關(guān)鍵字),則進(jìn)行交換則進(jìn)行交換,直到?jīng)]有反序的記錄為止。直到?jīng)]有反序的記錄為止。冒泡排序時(shí)間復(fù)雜度冒泡排序時(shí)間復(fù)雜度

12、最好情況最好情況( (正序正序) )：比較次數(shù)：比較次數(shù)：n-1n-1；移動(dòng)次數(shù)：；移動(dòng)次數(shù)：0 0； 最壞情況最壞情況( (逆序逆序) )：冒泡排序算法分析冒泡排序算法分析比較次數(shù)：比較次數(shù)：(n-i)=n-1i=1n(n-1)2移動(dòng)次數(shù)：移動(dòng)次數(shù)：3(n-i)=n-1i=13n(n-1)2時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：T(n)=O(n)T(n)=O(n)空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1)S(n)=O(1)穩(wěn)定性：穩(wěn)定相鄰元素的比較與交換）穩(wěn)定性：穩(wěn)定相鄰元素的比較與交換）2.快速排序算法思想：快速排序算法思想：是一種遞歸算法是一種遞歸算法,每次根據(jù)某個(gè)值每次根據(jù)某個(gè)值,將待排序列分成兩部

13、分將待排序列分成兩部分,一部分序列的元素一部分序列的元素關(guān)鍵字比該值小關(guān)鍵字比該值小,另一部分序列的元素關(guān)鍵字比該值大或等于）另一部分序列的元素關(guān)鍵字比該值大或等于）,然后再分別然后再分別對(duì)這兩部分進(jìn)行如上操作對(duì)這兩部分進(jìn)行如上操作,直至排序完成。直至排序完成。j前移前移2個(gè)位置后個(gè)位置后,Rj放在放在Ri的位置的位置:29 23 38 22 45 67 31ij初始關(guān)鍵字序列初始關(guān)鍵字序列:j29 29 38 22 45 23 67 31i029 23 22 45 38 67 31iji后移后移1個(gè)位置后個(gè)位置后,Ri放在放在Rj的位置的位置:29 23 22 45 38 67 31ijj前

14、移前移2個(gè)位置后個(gè)位置后,Rj放在放在Ri的位置的位置:29 23 22 29 45 38 67 31i ji后移后移1個(gè)位置后個(gè)位置后,i和和j的位置重合的位置重合:設(shè)有設(shè)有6個(gè)待排序的記錄個(gè)待排序的記錄,關(guān)鍵字分別為關(guān)鍵字分別為29, 38, 22, 45, 23, 67,一趟快速排序的過(guò)程如一趟快速排序的過(guò)程如圖所示：圖所示：快速排序的平均性能為快速排序的平均性能為O(nlog2n),在同數(shù)量級(jí)算法中綜合考慮在同數(shù)量級(jí)算法中綜合考慮,是最是最好的一種內(nèi)部排序方法好的一種內(nèi)部排序方法快速排序算法在最壞情況下待排序列正序或逆序）快速排序算法在最壞情況下待排序列正序或逆序）,每次劃分只得每次劃

15、分只得到比上一次少到比上一次少 一個(gè)記錄的子序列一個(gè)記錄的子序列,另一個(gè)子序列卻為空另一個(gè)子序列卻為空,即劃分得極不即劃分得極不均勻均勻,此時(shí)需要執(zhí)行此時(shí)需要執(zhí)行n-1次遞歸調(diào)用次遞歸調(diào)用,且比較的次數(shù)是且比較的次數(shù)是n(n-1)/2, 所以快所以快速排序收到序列初始狀態(tài)的影響速排序收到序列初始狀態(tài)的影響,在最壞情況下算法時(shí)間復(fù)雜度為在最壞情況下算法時(shí)間復(fù)雜度為O(n2)快速排序算法分析快速排序算法分析快速排序算法關(guān)鍵字的比較和交換也是跳躍式進(jìn)行的快速排序算法關(guān)鍵字的比較和交換也是跳躍式進(jìn)行的,所以快速排序所以快速排序算法也是一種不穩(wěn)定的排序方法。算法也是一種不穩(wěn)定的排序方法。由于進(jìn)行了遞歸調(diào)

16、用由于進(jìn)行了遞歸調(diào)用,需要一定數(shù)量的棧需要一定數(shù)量的棧O(log2n)作為輔助空間作為輔助空間例如例如1、快速排序算法在 數(shù)據(jù)元素按關(guān)鍵字有序的 情況下最不利于發(fā)揮其長(zhǎng)處。2、設(shè)關(guān)鍵字序列為：49,38,66,80,70,15,22,欲對(duì)該序列進(jìn)行從小到大排序。采用待排序列的第一個(gè)關(guān)鍵字作為樞軸,寫(xiě)出快速排序法的一趟和二趟排序之后的狀態(tài)答：第一趟之后：22, 38, 15, 49, 70, 80, 66 第二趟之后：15, 22, 38, 49, 66, 70, 80例例 給定給定 N = 10 個(gè)整數(shù)，范圍介于個(gè)整數(shù)，范圍介于 0 到到 999 ( M = 1000 ) 之間。是否可以在之間

17、。是否可以在線性的時(shí)間內(nèi)把它們排序線性的時(shí)間內(nèi)把它們排序 ? 單關(guān)鍵字的基數(shù)單關(guān)鍵字的基數(shù)排序排序輸入輸入: 64, 8, 216, 512, 27, 729, 0, 1, 343, 1250桶：桶：123456789（3位數(shù)可以看成個(gè)位數(shù)可以看成個(gè)3關(guān)鍵字，關(guān)鍵字，再按再按“次位優(yōu)先法排序）次位優(yōu)先法排序）0輪次輪次 1151234364125216278729輪次輪次 20151234364125216278729輪次輪次 30185122161252772934364輸出輸出: 0, 1, 8, 27, 64, 125, 216, 343, 512, 729時(shí)間復(fù)雜性：時(shí)間復(fù)雜性：T=O

18、(D(N+R) 其中其中D是輪次是輪次, N 是元素個(gè)數(shù)是元素個(gè)數(shù), R 是桶的數(shù)量是桶的數(shù)量.空間復(fù)雜性：空間復(fù)雜性：S=O(N+R) ,N 是元素個(gè)數(shù)是元素個(gè)數(shù), R 是桶的數(shù)量是桶的數(shù)量.穩(wěn)定性：穩(wěn)定穩(wěn)定性：穩(wěn)定用鏈?zhǔn)絻?chǔ)存更便于分配與收集用鏈?zhǔn)絻?chǔ)存更便于分配與收集南航南航2019年年二、解答題二、解答題(共共80分，分，8題，每題題，每題10分分)23已知數(shù)據(jù)序列為已知數(shù)據(jù)序列為(86，8，234，50，116，64，68，453，24，142)，給出，給出基數(shù)排序過(guò)程的示意圖?；鶖?shù)排序過(guò)程的示意圖。0桶：桶：123456789輪次輪次 2081161426424輪次輪次 382450234116648668輸出輸出: 8, 24, 50, 64, 68, 86, 116, 142, 234, 453南航南航2019年年4（10分已知數(shù)據(jù)序列為分已知數(shù)據(jù)序列為(76，58，234，5，16，164, 28，423，24，102) ，給出基數(shù)排序過(guò)程的示意圖。給出基數(shù)排序過(guò)程的示意圖。50輪次輪次 11424532348686411668245045323