數(shù)據(jù)庫結(jié)構(gòu)ppt課件-展示頁
2025-05-09 18:24本頁面
【正文】 216。R平均： O(n2)216。三、效率分析三、效率分析216。有序區(qū)也可從數(shù)據(jù)表的尾部生成 。初始取第 1條記錄為有序區(qū)，其它記錄為無序區(qū)。最終無序區(qū)為空，有序區(qū)包含了全部記錄，排序結(jié)束。一、基本思想一、基本思想 每次將無序區(qū)第 1條記錄插入到有序區(qū)適當位置。216。比較一般都需要，但移動可改變存儲方式來避免。R當鍵值是字串時，比較要占用較多的時間；R當記錄很大時，交換記錄時移動要占較多時間。216。附加空間一般不大，排序經(jīng)常執(zhí)行，時間開銷是最重標志。插入排序 (直插排序、二分排序、希爾排序 )交換排序 (冒泡排序、快速排序 )選擇排序 (直選排序、樹型排序、堆排序 )歸并排序 (二路歸并排序、多路歸并排序 )分配排序 (多關(guān)鍵字排序、基數(shù)排序 )內(nèi)排序評價標準：1） 時間 ；2） 附加空間 。待排序列： 49,38,65,97,76,13,27,49 排序后： 13,27,38,49,49,65,76,97 — 穩(wěn)定 ?排序后： 13,27,38,49,49,65,76,97— 不穩(wěn)定內(nèi)排序 ：排序過程全部在內(nèi)存中進行。降序表／逆序表：一、概念一、概念穩(wěn)定排序 ： 鍵值相同的記錄，排序后相對次序總能保持不變。無序表：216。216。排序 (Sorting)：簡單地說，就是將一組記錄按關(guān)鍵字域遞增 (由小到大 )或遞減 (由大到小 )的次序重新排列。216。 基本概念216。關(guān)鍵字 (key)：記錄中可用來標識一個記錄的數(shù)據(jù)項或其組合。第 7章 排序 基本概念基本概念 插入排序插入排序 交換排序交換排序 選擇排序選擇排序 歸并排序歸并排序 分配排序分配排序 內(nèi)排序的比較和選擇內(nèi)排序的比較和選擇* 外排序簡介外排序簡介排序就是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。排序的目的是為了方便以后的查找。關(guān)鍵字也簡稱 鍵 ，它的值稱為 鍵值 。主關(guān)鍵字 (Primary Key)：可唯一標識記錄的關(guān)鍵字，即不同記錄該關(guān)鍵字的值不同。次關(guān)鍵字 (Secondary Key)：不能唯一標識記錄的關(guān)鍵字。排序碼 (Sort Key)：作為排序依據(jù)的關(guān)鍵字。有序表：216。升序表／正序表：216。不穩(wěn)定排序： 鍵值相同記錄排序前后相對次序不能保持不變。外排序：排序過程需要進行內(nèi)存和外存之間的數(shù)據(jù)交換。3）算法的穩(wěn)定性、復雜程度等216。兩種基本操作：1） 比較 ：比較關(guān)鍵字的大小2） 移動 ：將記錄從一個位置移動到另一個位置。時間開銷主要指關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)。216。 二、時空分析二、時空分析 插入排序基本思想：依次將待排記錄插入到有序區(qū)適當位置，直到全部記錄插入完畢。初始有序區(qū)只有一個元素。隨著排序進行，有序區(qū)不斷擴大，無序區(qū)不斷縮小。216。216。 直接插入排序 (Straight Insertion Sort)二分插入二路插入 初始：（ 49） 38 13 76 27 49 （ 38 49） 13 76 27 49 （ 13 38 49） 76 27 49 （ 13 38 49 76） 27 49 （ 13 27 38 49 65） 49 （ 13 38 49 49 65 97）例 1：對 (49, 38, 13, 76, 65, 97, 27, 49 )直接插入排序。時間：R最好：正序， n1趟插入，每趟比較 1次，移動 0次： Cmin=n1=O(n)， Mmin=0R最壞：逆序，每趟比較 i1次，移動 i1
教學課件相關(guān)推薦
鄂ICP備17016276號-1