數(shù)據(jù)結(jié)構(gòu)第十章ppt課件(已修改)
2025-05-16 23:32 本頁(yè)面
【正文】 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容 1 排序： 將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新 排列成一個(gè)按關(guān)鍵字有序的序列 內(nèi)部排序： 將待排記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器重進(jìn) 行的排序過(guò)程。 外部排序： 由于待排記錄的數(shù)量很大，以至內(nèi)存一次 不能容納全部記錄，在排序過(guò)程中尚需要 對(duì)外存進(jìn)行訪問的排序過(guò)程。 2 第十章 內(nèi)部排序 第 10章 內(nèi)部排序 3 概述 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 4 概述 排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組 “ 無(wú)序 ” 的記錄序列調(diào)整為 “ 按關(guān)鍵字有序 ” 的記錄序列。 52， 49， 80， 36， 14， 58， 61， 23， 97， 75 14， 23， 36， 49， 52， 58， 61， 75， 80， 97 一般情況下， 假設(shè)含 n個(gè)記錄的序列為 {R1， R2， …… ， Rn} 其相應(yīng)的關(guān)鍵字序列為 {K1， K2， …… ， Kn} 這些關(guān)鍵字相互之間可以進(jìn)行比較， 即在它們之間存在這樣一個(gè)關(guān)系： Kp1=Kp2=… =Kpn 按此固有關(guān)系將上式記錄序列重新排列為 {Rp1,Rp2,… ,Rpn}的操作稱作排序 5 關(guān)鍵字 數(shù)據(jù)對(duì)象有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可以用來(lái)區(qū)分對(duì)象，作為排序依據(jù)，稱為 關(guān)鍵字 。 關(guān)鍵字與記錄之間是一對(duì)一的關(guān)系 稱 主關(guān)鍵字 關(guān)鍵字與記錄之間是一對(duì)多的關(guān)系 稱 次關(guān)鍵字 6 排序的目的是什么？ —— 便于查找 排序算法的好壞如何衡量？ ? 時(shí)間效率 —— 排序速度（即排序所花費(fèi)的全部比較次數(shù)） ? 空間效率 —— 占內(nèi)存輔助空間的大小 ? 穩(wěn)定性 —— 若兩個(gè)記錄 A和 B的關(guān)鍵字相等，但排序后 A， B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。 7 什么叫內(nèi)部排序？什么叫外部排序 —— 若待排序記錄都在內(nèi)存中，稱內(nèi)部排序 —— 若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。 注：外部排序時(shí)，要將數(shù)據(jù)分批掉入內(nèi)存來(lái)排序，中間結(jié)果還要及時(shí)放入內(nèi)存，顯然外部排序要復(fù)雜得的多。 8 待排序記錄在內(nèi)存中怎樣存儲(chǔ)和處理 （ 1） 順序排序 —— 排序時(shí)直接移動(dòng)記錄； （ 2）鏈表排序 —— 排序時(shí)只移動(dòng)指針； （ 3）地址排序 —— 排序時(shí)先移動(dòng)地址，最后再移動(dòng)記錄。 注：地址排序中可以增設(shè)一維數(shù)組來(lái)專門存放記錄的地址。 9 注： 大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的 (便于直接移動(dòng)元素 ) Typedef struct { //定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu) KeyType key 。 //關(guān)鍵字 InfoType otherinfo。 //其它數(shù)據(jù)項(xiàng) }RecordType 。 Typedef struct { //定義順序表的結(jié)構(gòu) RecordType r [ MAXSIZE +1 ]。 //存儲(chǔ)順序表的向量 //r[0]一般作哨兵或緩沖區(qū) int length 。 //順序表的長(zhǎng)度 }SqList 。 define MAXSIZE 20 //設(shè)記錄不超過(guò) 20個(gè) typedef int KeyType 。 //設(shè)關(guān)鍵字為整型量（ int型） 10 —— 按排序的規(guī)則不同，可分為 5類： ? 插入排序 ? 交換排序（重點(diǎn)是快速排序） ? 選擇排序 ? 歸并排序 ? 基數(shù)排序 d＝關(guān)鍵字的位數(shù) (長(zhǎng)度 ) —— 按排序算法的時(shí)間復(fù)雜度不同，可分為 3類： ?簡(jiǎn)單的排序算法：時(shí)間效率低， O(n2) ?先進(jìn)的排序算法 : 時(shí)間效率高， O( nlog2n ) ?基數(shù)排序算算法：時(shí)間效率高， O( d n) 11 插入排序的基本思想是： 插入排序有多種具體實(shí)現(xiàn)算法： 1) 直接插入排序 2) 折半插入排序 3) 表插入排序 4) 希爾排序 每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小， 插入到前面 已經(jīng)排好序的一組對(duì)象的適當(dāng)位置 上 ，直到對(duì)象全部插入為止。 簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。 12 ? 基本思想： ? 假定前面 m 個(gè)元素已經(jīng)排序； ? 取第 (m+1) 個(gè)元素，插入到前面的適當(dāng)位置； ? 一直重復(fù)，到 m=n 為止。 ? （初始情況下， m = 1） 13 例 1： 關(guān)鍵字序列 T=（ 13， 6， 3， 31， 9， 27， 5， 11）， 請(qǐng)寫出直接插入排序的中間過(guò)程序列。 【 13】 , 6, 3, 31, 9, 27, 5, 11 【 6, 13】 , 3, 31, 9, 27, 5, 11 【 3, 6, 13】 , 31, 9, 27, 5, 11 【 3, 6, 13， 31】 , 9, 27, 5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1