26排序問題和插入排序(45頁)-全文預覽
【正文】 2 3 4 5 6 7 49 65 76 97 13 27 38 0 1 2 3 4 5 6 7 13 i=6: 49 38 65 76 97 13 38 49 65 76 97 27 13 0 1 2 3 4 5 6 7 27 i=7: 49 38 65 76 97 27 直接插入排序性能分析 實現內部排序的基本操作有兩個： 2）“移動”記錄。 // 復制為監(jiān)視哨 for ( j=i1。L ) { // 對順序表 L 作直接插入排序。 j)。 2． 將 R[j+1..i1]中的所有 記錄 均 后移 一個位置； 1． 在 R[1..i1]中 查找 R[i]的插入位置， R[1..j].key ? R[i].key R[j+1..i1].key； 插入排序分類 （ 基于順序查找 ） （ 基于折半查找 ） （ 基于逐趟縮小增量 ） 根據不同的具體查找方法 直接插入排序 基本操作： 將一個記錄插入到已經排好序的有序表中。 // 記錄類型 內部排序方法的分類 typedef struct { RcdType r[MAXSIZE+1]。 各種排序方法的定義 內部排序方法的分類 define MAXSIZE 1000 // 待排順序表最大長度 typedef int KeyType。 各種排序方法的定義 交換排序：通過 “ 交換 ” 無序序列中的記錄從而得到其中關鍵字 最小或最大 的記錄，并將它 加入到有序子序列 中，以此方法增加記錄的有序子序列的長度。 內部排序和外部排序 由于待排序的記錄數量不同，使得排序過程中涉及的存儲器不同，可將排序方法分為： ：整個排序過程不需要訪問外存 便能完成。 排序的定義 關鍵字 (key): 數據對象有多個屬性域 , 即多個數據成員組成 , 其中有一個屬性域可用來區(qū)分對象 , 作為排序依據，稱為 關鍵字 。 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≤…≤K pn 按此固有關系將上式記錄序列重新排列為 { Rp1, Rp2, … ， Rpn } 的操作稱作 排序 。 如果在排序之后 , 對象 r[i]仍在對象 r[j]的前面 , 則稱這個排序方法是 穩(wěn)定的 , 否則稱這個排序方法是 不穩(wěn)定的。 有序序列區(qū) 無 序 序 列 區(qū) 有序序列區(qū) 無 序 序 列 區(qū) 內部排序方法的分類 基于不同的“ 擴大 ” 有序序列長度的 方法，內部排序方法 大致可分下列幾種類型： 內部
教學課件相關推薦
鄂ICP備17016276號-1