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