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