數(shù)據(jù)庫(kù)結(jié)構(gòu)ppt課件-資料下載頁(yè)
2025-04-30 18:24本頁(yè)面
【正文】 表，兩兩歸并，得到 ?n/2? 個(gè)有序的子表 (當(dāng) n為奇數(shù)時(shí)，歸并后仍有一個(gè)長(zhǎng)度為 1的子表 )；再把這些有序子表兩兩歸并，如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為 n的有序表為止。 歸并排序 (Merging Sort)利用 “ 歸并 ” 技術(shù)來進(jìn)行排序，所謂歸并是指將若干個(gè)已排序的子表合并成一個(gè)有序表。 例 對(duì) (49, 38, 65, 97, 76, 13, 49’)二路歸并排序。比較：歸并時(shí)子表不斷變大；快排時(shí)子表不斷化小。763 163 88R：R1：i j5416 79例 兩子表合并 k三．效率分析三．效率分析216。子表長(zhǎng)度不斷加倍， 1→n ，歸并趟數(shù)為 ?log2n?； 每趟歸并比較次數(shù) ?移動(dòng)次數(shù)，后者為 O(n)；總時(shí)間復(fù)雜度 O(nlog2n)。216。輔助空間為數(shù)組 R1，空間復(fù)雜度 O(n)216。鍵值相同記錄順序復(fù)制，不改變相對(duì)位置，故是穩(wěn)定的。216?？稍阪湵砩蠈?shí)現(xiàn) 分配排序216。利用關(guān)鍵字結(jié)構(gòu)，通過 “ 分配 ” 和 “ 收集 ” 實(shí)現(xiàn)排序216。無需比較關(guān)鍵字。216?？煞譃橄渑判蚝突鶖?shù)排序兩類。 箱排序、桶排序 (Bin Sort、 Bucket Sort)設(shè)置若干箱子，掃描待排記錄 R[1]、 R[2]、 … 、 R[n]，把關(guān)鍵字等于 k的記錄全都裝入到第 k個(gè)箱子 (分配 )，然后，按序號(hào)依次將各非空的箱子首尾連接起來 (收集 )。 例，撲克牌按面值 A2… JQK排序 (不分花色 )，設(shè)置 13個(gè) “箱子 ”，依次將每張牌按面值放入相應(yīng)的箱子里，然后依次將箱子首尾相接，就得到按面值遞增序排列的一副牌。 216。箱子個(gè)數(shù) m取決于關(guān)鍵字的取值范圍。216。分配時(shí)間 O(n)，收集時(shí)間 O(m+n)（若用鏈表，則 O(m)），所以箱排序時(shí)間 O(m+n)。216。若關(guān)鍵字的取值范圍很大，如 m=O(n2)，則效率很低。 基數(shù)排序 (Radix Sort)216。多關(guān)鍵字排序：低位優(yōu)先，高位優(yōu)先 ?216。每趟箱子共用，每趟排序前清空箱子（除第一趟外）216。箱子的數(shù)據(jù)按隊(duì)列存放 216。箱子內(nèi)數(shù)據(jù)個(gè)數(shù)可變，適合鏈表實(shí)現(xiàn)－鏈?zhǔn)交鶖?shù)排序?qū)㈥P(guān)鍵字看成多個(gè)分量組成，從低到高依次對(duì)關(guān)鍵字的各分量進(jìn)行箱排序，每趟所需箱子數(shù)就是基數(shù)。 216。時(shí)間：鏈表初始化 O(n)，清箱 O(r)，收集 O(r)，分箱 O(n)，一趟總 O(n+r)， d趟總 O(d(n+r))→O(n )。216?？臻g：結(jié)點(diǎn)指針 O(n)，箱子頭尾指針 O(r)，總 O(n+r)216。穩(wěn)定：分配和收集不改變相同鍵值的相對(duì)位置。例 對(duì) (91, 46, 85, 15, 92, 35, 31, 22)基數(shù)排序0 1 2 3 4 5 6 7 8 991 468515923531 22收集： 91 31 92 22 85 15 35 460 1 2 3 4 5 6 7 8 991319222 85153546收集： 15 22 31 35 46 85 91 92分配(按個(gè)位)分配(按十位) 內(nèi)排序的比較和選擇簡(jiǎn)單排序 (直接插入、直接選擇、冒泡排序等 )每次只對(duì)相鄰元素比較，前進(jìn)步伐慢，時(shí)間耗費(fèi)大，為 O(n2)，但一些特殊情況卻可取得很好效果；效率高的算法每次比較產(chǎn)生的作用不僅僅局限于被比較的兩個(gè)元素，而是多個(gè)甚至一半左右，但它們對(duì)數(shù)據(jù)量小的情況并不一定合適。 綜合考慮下列因素：(1)待排序的記錄數(shù)目。(2)記錄本身信息量的大小。(3)關(guān)鍵字的結(jié)構(gòu)及其分布情況。(4)對(duì)排序穩(wěn)定性的要求。(5)語言工具的條件。(6)算法本身的難易程度。(7)輔助空間的大小等。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1