【正文】 數(shù) 據(jù) 結(jié) 構(gòu)—— With C/C++主講教師：石振鋒主講教師：石振鋒哈爾濱工業(yè)大學數(shù)學系哈爾濱工業(yè)大學數(shù)學系2022年 6月1數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 概述 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序第 9章 內(nèi)部排序數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 概述1. 什么是排序？ 將一組雜亂無章的 數(shù)據(jù) 按一定的 規(guī)律 順次排列起來。 2. 排序的目的是什么？存放在數(shù)據(jù)表中 按 關(guān)鍵字排序？? 時間效率 —— 排序速度（即排序所花費的全部比較次數(shù)）? 空間效率 —— 占內(nèi)存輔助空間的大小? 穩(wěn)定性 —— 若兩個記錄 A和 B的關(guān)鍵字值相等，但排序后 A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。 —— 便于查找！數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 4. 什么叫內(nèi)部排序？什么叫外部排序 ？ —— 若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；—— 若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。注： 外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時放入外存，顯然外部排序要復(fù)雜得多。 ？① 順序 排序 —— 排序時直接移動記錄；② 鏈表 排序 —— 排序時只移動指針；③ 地址 排序 —— 排序時先移動地址，最后再移動記錄。注： 地址排序 中可以增設(shè)一維數(shù)組來專門存放記錄的地址。數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 注： 大多數(shù)排序算法都是針對順序表結(jié)構(gòu)的 (便于直接移動元素)6. 順序存儲（順序表）的抽象數(shù)據(jù)類型如何表示？Typedef struct { //定義每個記錄（數(shù)據(jù)元素）的結(jié)構(gòu) KeyType key 。 //關(guān)鍵字 InfoType otherinfo。 //其它數(shù)據(jù)項}RecordType 。Typedef struct { //定義順序表的結(jié)構(gòu) RecordType r [ MAXSIZE +1 ]。 //存儲順序表的向量 //r[0]一般作哨兵或緩沖區(qū) int length 。 //順序表的長度}SqList 。 define MAXSIZE 20 //設(shè)記錄不超過 20個typedef int KeyType 。 //設(shè)關(guān)鍵字為整型量（ int型）數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 7. 內(nèi)部排序的算法有哪些？—— 按排序的規(guī)則不同，可分為 5類：? 插入排序? 交換排序（重點是快速排序）? 選擇排序? 歸并排序? 基數(shù)排序d＝ 關(guān)鍵字的位數(shù) (長度 )—— 按排序算法的時間復(fù)雜度不同，可分為 3類：?簡單的排序算法：時間效率低， O(n2)?先進的排序算法 : 時間效率高， O( nlog2n )?基數(shù)排序算算法：時間效率高， O( dn)數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 插入排序插入排序的基本思想是：插入排序的基本思想是：插入排序有多種具體實現(xiàn)算法： 1) 直接插入排序 2) 折半插入排序 3) 表插入排序 4) 希爾排序 每步將一個待排序的對象，每步將一個待排序的對象，按其關(guān)鍵碼大小，按其關(guān)鍵碼大小， 插入到前面插入到前面 已經(jīng)排好序的一組對象已經(jīng)排好序的一組對象的的 適當位置適當位置 上上 ，直到對象全部插入為止。，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 1) 直接插入排序新元素插入到哪里？例 1： 關(guān)鍵字序列 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, 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】 在已形成的 有序表中 線性查找 ，并在適當位置插入，把原來位置上的元素向后 順移 。最簡單的排序法！最簡單的排序法！數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 例 2： 關(guān)鍵字序列 T= （ 21， 25， 49， 25*， 16， 08），請寫出直接插入排序的具體實現(xiàn)過程。 *表示后一個 25i=121 25 49 25* 16 080 1 2 3 4 5 6暫暫存存i=2 i=3 i=5i=4 i=6254925* 4916 25*08 49解： 假設(shè)該序列已存入一維數(shù)組 V[7]中，將 V[0]作為緩沖或暫存單元（ Temp）。 則程序執(zhí)行過程為：21 25 49初態(tài)：16 25*25211608完成完成 !時間效率： O(n2)—— 因為在最壞情況下，所有元素的比較次數(shù)總和為（ 0＋ 1＋ … ＋ n1)→O(n 2)。 其他情況下還要加上移動元素的次數(shù)。 空間效率： O（（ 1）） —— 因為僅占用 1個緩沖單元算法的穩(wěn)定性： 穩(wěn)定穩(wěn)定 —— 因為 25*排序后仍然在 25的后面。 對應(yīng)程序參見教材 P265。數(shù)學系計算數(shù)學教研室 數(shù)據(jù)結(jié)構(gòu) Ch02 n 若設(shè)待排序的對象個數(shù)為若設(shè)待排序的對象個數(shù)為 n， 則算法需要進行則算法需要進行 n1次插入。次插入。n 最好情況下，排序前對象已經(jīng)按關(guān)鍵碼大小從最好情況下，排序前對象已經(jīng)按關(guān)鍵碼大小從小到大有序，每趟只需與前面的有序?qū)ο?