26排序問題和插入排序(45頁)(已修改)
2025-05-14 13:19 本頁面
【正文】 排序問題和插入排序 排序問題 插入排序 小結(jié)和作業(yè) 排序的定義 內(nèi)部排序和外部排序 內(nèi)部排序方法的分類 排序問題 排序的定義 排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組 “ 無序 ” 的記錄序列調(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個記錄的序列為 { R1, R2, … ， Rn } 其相應(yīng)的關(guān)鍵字序列為 { K1, K2, … ， Kn } 這些關(guān)鍵字相互之間可以進行比較，即在 它們之間存在著這樣一個關(guān)系 ： Kp1≤Kp2≤…≤K pn 按此固有關(guān)系將上式記錄序列重新排列為 { Rp1, Rp2, … ， Rpn } 的操作稱作 排序 。 排序的定義 關(guān)鍵字 (key): 數(shù)據(jù)對象有多個屬性域 , 即多個數(shù)據(jù)成員組成 , 其中有一個屬性域可用來區(qū)分對象 , 作為排序依據(jù)，稱為 關(guān)鍵字 。也稱為 排序碼 。 排序的定義 排序方法的穩(wěn)定性 : 如果在對象序列中有兩 個對象 r[i]和 r[j], 它們的排序碼 k[i] = k[j] , 且在排序之前 , 對象 r[i]排在 r[j]前面。 如果在排序之后 , 對象 r[i]仍在對象 r[j]的前面 , 則稱這個排序方法是 穩(wěn)定的 , 否則稱這個排序方法是 不穩(wěn)定的。 內(nèi)部排序和外部排序 由于待排序的記錄數(shù)量不同，使得排序過程中涉及的存儲器不同，可將排序方法分為： ：整個排序過程不需要訪問外存 便能完成。 ： 參加排序的記錄數(shù)量很大，整個序列的排序過程 不可能在內(nèi)存中完成。 內(nèi)部排序方法的分類 內(nèi)部排序的過程是一個 逐步擴大 記錄的 有序序列長度 的過程。 有序序列區(qū) 無 序 序 列 區(qū) 有序序列區(qū) 無 序 序 列 區(qū) 內(nèi)部排序方法的分類 基于不同的“ 擴大 ” 有序序列長度的 方法，內(nèi)部排序方法 大致可分下列幾種類型： 內(nèi)部排序方法 插入排序： 將無序子序列中的 一個或幾個記錄“ 插入 ”到有序序列中，從而增加記錄的有序子序列的長度。 各種排序方法的定義 交換排序：通過 “ 交換 ” 無序序列中的記錄從而得到其中關(guān)鍵字 最小或最大 的記錄，并將它 加入到有序子序列 中，以此方法增加記錄的有序子序列的長度。 選擇排序： 從記錄的無序子序列中 “ 選擇 ” 關(guān)鍵字 最小或最大 的記錄，并將它加入到 有序子序列中 ，以此方法增加記錄的有序子序列的長度。 各種排序方法的定義 歸并排序： 通過 “ 歸并 ” 兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。 基數(shù)排序： 是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行排序的方法。 各種排序方法的定義 內(nèi)部排序方法的分類 define MAXSIZE 1000 // 待排順序表最大長度 typedef int KeyType。 // 關(guān)鍵字類型為整數(shù)類型 待排記錄的數(shù)據(jù)類型定義如下 : typedef struct { KeyType key。 // 關(guān)鍵字項 InfoType otherinfo。 // 其它數(shù)據(jù)項 } RcdType。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1