數(shù)據(jù)庫結(jié)構(gòu)ppt課件(參考版)
2025-05-03 18:24本頁面
【正文】 (7)輔助空間的大小等。(5)語言工具的條件。(3)關(guān)鍵字的結(jié)構(gòu)及其分布情況。 綜合考慮下列因素：(1)待排序的記錄數(shù)目。穩(wěn)定：分配和收集不改變相同鍵值的相對位置。216。 216。箱子的數(shù)據(jù)按隊列存放 216。多關(guān)鍵字排序：低位優(yōu)先，高位優(yōu)先 ?216。若關(guān)鍵字的取值范圍很大，如 m=O(n2)，則效率很低。分配時間 O(n)，收集時間 O(m+n)（若用鏈表，則 O(m)），所以箱排序時間 O(m+n)。箱子個數(shù) m取決于關(guān)鍵字的取值范圍。 例，撲克牌按面值 A2… JQK排序 (不分花色 )，設(shè)置 13個 “箱子 ”，依次將每張牌按面值放入相應(yīng)的箱子里，然后依次將箱子首尾相接，就得到按面值遞增序排列的一副牌。可分為箱排序和基數(shù)排序兩類。無需比較關(guān)鍵字。可在鏈表上實現(xiàn) 分配排序216。鍵值相同記錄順序復(fù)制，不改變相對位置，故是穩(wěn)定的。216。763 163 88R：R1：i j5416 79例 兩子表合并 k三．效率分析三．效率分析216。 例 對 (49, 38, 65, 97, 76, 13, 49’)二路歸并排序。不穩(wěn)定，如 (2, 1, 2?)四、效率分析四、效率分析一、一、 二路歸并排序基本思想二路歸并排序基本思想 初始排序表看成 n個長度為 1的有序子表，兩兩歸并，得到 ?n/2? 個有序的子表 (當 n為奇數(shù)時，歸并后仍有一個長度為 1的子表 )；再把這些有序子表兩兩歸并，如此反復(fù)，直到最后得到一個長度為 n的有序表為止。輔助空間為 1(供交換用 )，空間復(fù)雜度為 O(1)。建堆 ?n/2? 篩選，重建 n?1次篩選，每次篩選雙親和孩子比較和移動，不超過深度，時間復(fù)雜度 (?n/2?+n?1)O(log2n)=O(nlog2n)。將其余的元素篩選成堆；16981621110 54交換 篩選交換篩選4981621110 5161198162104 5162981611104 516110 16211 45例，對 (1, 2, 9, 11, 4, 6, 8, 10, 16, 5)建初始堆 (大根 )。19810616211 5419810611216 5419810611216 54n=10，故從第 ?10/2? =5個結(jié)點開始進行調(diào)整 19810611162 5419810621611 5416981062111 5416981062111 5416981621110 54調(diào)整和重建216。按該次序調(diào)整各結(jié)點時，其左、右子樹均已是堆 (不妨將空樹亦看作是堆 )。216。216。如此反復(fù)，直到全部元素輸出完。二、堆排序基本思想二、堆排序基本思想利用小 (大 )根堆選取當前無序區(qū)關(guān)鍵字最小 (大 )的記錄來實現(xiàn)排序。為保證空間性能，輸出的堆頂應(yīng)利用原有空間，可將它與無序區(qū)最后記錄交換位置。堆中任一棵子樹也是堆 81691621110 5481691062111 5481611916210 4581910616211 54216。小根堆216。 1） 堆 是一棵完全二叉樹，任一結(jié)點關(guān)鍵字小于等
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1