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