【正文】 1 04/01/2022 1 2 第 7章 排序 基本概念 插入排序 交換排序 選擇排序 歸并排序 分配排序 各種內部排序比較 3 基本概念 假設含有 n個記錄的序列為 {R1， R2， … Rn} 其對應的關鍵字序列為 {K1， K2， … Kn} 根據 Ki的值對這組序列重新排列，使對應關鍵字有序 Ri為一條記錄 Ki為記錄的關鍵字 可能存在多條記錄具有相同的關鍵字 4 若具有相同關鍵字的記錄經過排序后記錄的相對位置 仍保持不變則該排序算法是穩(wěn)定的，否則為不穩(wěn)定的 排序時只在內存中進行，為內排序， 需要讀取外存設備中數據的為外排序 內部排序方法有： 插入排序，交換排序，選擇排序，歸并排序 評價排序算法優(yōu)劣的標準： 時間復雜度和空間復雜度 5 待排序記錄存儲結構： typedef struct { int key； antype otheritem； } records； typedef records list[n+1]。 //list 為定義待排序記錄的數據類型 //并規(guī)定待排序記錄中 0元素不存數據 6 插入排序 直接插入排序（基于順序查找） 表插入排序（基于鏈表存儲） 折半插入排序（基于折半查找） 希爾排序（基于逐趟縮小增量） 7 插入排序 直接插入排序（基于順序查找） 直接插入排序思想： 依次將待排序記錄中的第 i個記錄插入到有序序列中 . 初始情況：將 r1作為有序序列，將 r2rn逐個插入 , 通過順序查找方式找到 ri在有序表中的位置 , 找位置的同時移動有序序列中元素的位置 , 找位置時從后向前找 . 在一個已排好序的記錄子集的基礎上，每一步將下一個待排序的記錄有序地插入到已排好序的記錄子集中，直到將所有待排記錄全部插入為止。 8 直接插入排序（基于順序查找） 初始關鍵字 35 48 35 18 45 12 68 33 4835第一趟排序 48 35 18 45 12 68 33 步驟： i=2 ri存入 r0位置 將 r0關鍵字與 rj關鍵字比較（ j從 i1開始到 1） 若 r0rj則 rj存入 rj+1位置， j減 1 r0存入 rj+1位置 r0為監(jiān)視哨 9 直接插入排序（基于順序查找） 初始關鍵字 35 18 45 12 68 33 48 35 第二趟排序 48 35 18 45 12 68 33 步驟： i=3 ri存入 r0位置 將 r0關鍵字與 rj關鍵字比較（ j從 i1開始到 1） 若 r0rj則 rj存入 ri+1位置， j減 1 r0存入 rj+1位置 18 483518r0為監(jiān)視哨 10 直接插入排序（基于順序查找） 初始關鍵字 45 12 68 33 第三趟排序 48 35 18 45 12 68 33 步驟： i=4 ri存入 r0位置 將 r0關鍵字與 rj關鍵字比較（ j從 i1開始到 1） 若 r0rj則 rj存入 rj+1位置， j減 1 r0存入 rj+1位置 18 48 35 18 45 48 45r0為監(jiān)視哨 11 直接插入排序（基于順序查找） 初始關鍵字 12 68 33 第四趟排序 48 35 18 45 12 68 33 步驟： i=5 ri存入 r0位置 將 r0關鍵字與 rj關鍵字比較（ j從 i1開始到 1） 若 r0rj則 rj存入 rj+1位置， j減 1 r0存入 rj+1位置 35 18 45 48 45 12 48 453518 12 r0為監(jiān)視哨 12 直接插入排序（基于順序查找） 初始關鍵字 [48] 35 18 45 12 68 33 [35 48] 18 45 12 68 33 [18 35 48] 45 12 68 33 [18 35 45 48] 12 68 33 [12 18 35 45 48] 68 33 [12 18 35 45 48 68] 33 [12 18 33 35 45 48 68] 13 【 例 】 打撲克牌時的抓牌就是插入排序一個很好的例子，每抓一張牌，插入到合適位置，直到抓完牌為止，即可得到一個有序序列。 14 已知一組鍵值序列 （ 22， 24， 26， 25， 27， 29， 21， 28）， 試給出采用直接插入排序法對該組序列 作升序排序的每一趟結果 試寫出直接插入排序算法 設順序表 va中的數據元素遞增有序。試編寫算法實現將 x插入到順序表的適當位置上，以保持該表的有序性 用插入排序算法對數據序列 （ 47， 33， 61， 82， 72， 11， 25， 57） 進行排序，寫出整個插入排序的每一趟過程。 15 插入排序 直接插入排序（基于順序查找） Void StraightSort（ list r, int n） { for（ i=2； i=n。 i++） { r[0] = r[i]。 j = i1。 while ( r[0].key r[j].key ) { r[j+1] = r[j]。 j。 } r[j+1] = r[0]。 } } r0為監(jiān)視哨 該算法時間復雜度為 O（ n2） 該算法空間復雜度為 O（ 1） 該算法是穩(wěn)定的排序算法 16 設順序表 va中的數據元素遞增有序。試編寫算法實現將x插入到順序表的適當位置上，以保持該表的有序性 Va類型定義 typedef struct { int key； anytype others； } record； define maxsize