數(shù)據(jù)結(jié)構(gòu)課件第十章(已修改)
2025-05-29 00:10 本頁(yè)面
【正文】 1 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容 2 概述 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 第 十 章 內(nèi)部排序 3 概述 排序是計(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}的操作稱作排序 4 關(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)鍵字 5 排序的目的是什么？ —— 便于查找 排序算法的好壞如何衡量？ ? 時(shí)間效率 —— 排序速度（即排序所花費(fèi)的全部比較次數(shù)） ? 空間效率 —— 占內(nèi)存輔助空間的大小 ? 穩(wěn)定性 —— 若兩個(gè)記錄 A和 B的關(guān)鍵字相等，但排序后 A， B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。 6 什么叫內(nèi)部排序？什么叫外部排序 —— 若待排序記錄都在內(nèi)存中，稱內(nèi)部排序 —— 若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。 注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來(lái)排序，中間結(jié)果還要及時(shí)放入內(nèi)存，顯然外部排序要復(fù)雜得的多。 內(nèi)部排序和外部排序的不同在于能否一次處理完所有數(shù)據(jù) 7 排序主要做的工作： 比較 + 移動(dòng) 8 7. 內(nèi)部排序的算法有哪些？ —— 按排序的規(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) 9 插入排序 插入排序的基本思想是： 插入排序有多種具體實(shí)現(xiàn)算法： 1) 直接插入排序 2) 折半插入排序 3) 希爾排序 每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小， 插入到前面 已經(jīng)排好序的一組對(duì)象的適當(dāng)位置 上 ，直到對(duì)象全部插入為止。 簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。 10 1) 直接插入排序 新元素插入到哪里？ 例 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, 11 【 3, 6, 9, 13， 31】 , 27, 5, 11 【 3, 6, 9, 13， 27, 31】 , 5, 11 【 3, 5, 6, 9, 13， 27, 31】 , 11 【 3, 5, 6, 9, 11， 13， 27, 31】 在已形成的 有序表中線性查找 ，并在適當(dāng)位置插入，把原來(lái)位置上的元素向后 順移 。 最簡(jiǎn)單的排序法！ 11 –例題 對(duì)下列存放在數(shù)組 A中的序列采用直接插入排序法排序。 49 38 65 97 13 76 27 49 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 監(jiān)視哨 注 紫色 表示待排數(shù)據(jù)； 藍(lán)色 表示已經(jīng)有序數(shù)據(jù) 49 38 第 趟插入排序 1 待排元素 38 38 65 2待排元素 49 97 3待排元素 76 4待排元素 76 765待排元素 97 13 13 13 97 27 6待排元素 27 6549 27待排元素 797 49 766549 4949排序趟數(shù) =數(shù)據(jù)個(gè)數(shù) 1 12 2） 折半插入排序 優(yōu)點(diǎn)： 比較的次數(shù)大大減少 ， 全部元素比較次數(shù)僅為 O(nlog2n)。 時(shí)間效率： 雖然比較次數(shù)大大減少 ， 可惜移動(dòng)次數(shù)并未減少 ，所以排序效率仍為 O(n2) 。 空間效率： O（ 1） 穩(wěn)定性： 穩(wěn)定 對(duì)應(yīng)程序見(jiàn)教材 P267（ 僅用于順序表 ） 新元素插入到哪里？ 討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？ 答： 直接插入不僅可行，而且還無(wú)需移動(dòng)元素，時(shí)間效率更高！ 在已形成的 有序表中折半查找 ，并在適當(dāng)位置插入，把原來(lái)位置上的元素向后 順移 。 但鏈表無(wú)法 “ 折半 ” ！ 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, 11 【 3, 6, 9, 13， 31】 , 27, 5, 11 【 3, 6, 9, 13， 27, 31】 , 5, 11 【 3, 5, 6, 9, 13， 27, 31】 , 11 【 3, 5, 6, 9, 11， 13， 27, 31】 14 例：有 6個(gè)記錄 ， 前 5 個(gè)已排序的基礎(chǔ)上 ， 對(duì)第 6個(gè)記錄排序 。 [ 15 27 36 53 69 ] 42 ? low ?mid ? high
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1