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