26排序問(wèn)題和插入排序(45頁(yè))-資料下載頁(yè)
2025-04-24 13:19本頁(yè)面
【導(dǎo)讀】序”的記錄序列。假設(shè)含n個(gè)記錄的序列為{R1,R2,…其相應(yīng)的關(guān)鍵字序列為{K1,K2,…的操作稱(chēng)作排序。為排序依據(jù)，稱(chēng)為關(guān)鍵字。如果在排序之后,對(duì)象r[i]仍在對(duì)象r[j]的前面,方法是不穩(wěn)定的。列的排序過(guò)程不可能在內(nèi)存中完成。子序列，逐步增加記錄有序序列的長(zhǎng)度。3．將R[i]插入(復(fù)制)到R[j+1]的位置上。1．在R[1..i-1]中查找R[i]的插入位置，從R[i-1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在R[0]；//對(duì)順序表L作直接插入排序。2）“移動(dòng)”記錄。1）“比較”序列中兩個(gè)關(guān)鍵字的大小；
【正文】 key [idk].key) { [0] = [i]。 // 暫存在 R[0] for (j=idk。 j0amp。amp。([0].key[j].key)。 j=dk) [j+dk] = [j]。 // 記錄后移，查找插入位置 [j+dk] = [0]。 // 插入 } // if } // ShellInsert 希爾排序 void ShellSort (SqList amp。L, int dlta[], int t) { // 增量為 dlta[]的希爾排序 for (k=0。 kt。 ++t) ShellInsert(L, dlta[k])。 //一趟增量為 dlta[k]的插入排序 } // ShellSort 希爾排序 算法描述舉例 int d[]={5,3,1}。 1 2 3 4 5 6 7 8 9 10 38 65 97 76 13 27 49 55 04 49 38 65 97 7613 27 49 55 04 49 j i j i j i j i j i 第一趟 [0].key= 13 27495504dk=d[0]=5 希爾排序 算法描述舉例 int d[]={5,3,1}。 1 2 3 4 5 6 7 8 9 10 27 49 55 04 49 38 65 97 76 13 27 04 j i j i 38 55 j i j i j i j i j i 第二趟 [0].key= dk=d[1]=3 04 38j j+dk 希爾排序 算法描述舉例 int d[]={5,3,1}。 1 2 3 4 5 6 7 8 9 10 04 49 38 27 49 55 65 97 76 13 38 04j i 13 49 第二趟 [0].key= dk=d[2]=1 04 38j i j i j j i 2749 j 3827j i j i j i j i j i 97j 76j+dk j+dk 76 j+dk 希爾排序 算法分析： 增量序列可以有各種取法，但序列中最后 1個(gè)值必須是 1，序列中的值沒(méi)有除 1以外的公因子。 不是穩(wěn)定的算法 希爾排序 用希爾排序?qū)?shù)組 {98， 36， 9， 0， 47，23， 1， 8， 10， 7}進(jìn)行排序，給出的步長(zhǎng)依次是 5， 3， 1，寫(xiě)出前兩趟趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序 小結(jié)和作業(yè) 本次課主要介紹了： 1． 定義 2． 分類(lèi) 3． 穩(wěn)定性和存儲(chǔ)方式 4． 排序算法的評(píng)價(jià) 小結(jié)和作業(yè) 本次課主要介紹了： 1． 基本思想 2． 實(shí)例模擬 3． 算法描述 4． 算法的復(fù)雜度 作業(yè)： (1， 2)， （思考）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1