[工學(xué)]數(shù)據(jù)結(jié)構(gòu)第23講_插入排序2和交換排序_c-展示頁
2024-10-28 00:03本頁面
【正文】 or (k=0。 // 記錄后移 ， 查找插入位置 [j+dk] = [0]。 ([0].key [j].key)。 j0 amp。 ++i ) if ( [i].key [idk].key) {//將 R[i]插入有序增量子表 [0] = [i]。 當(dāng) j=0時(shí) ， 插入位置已找到 for ( i=dk+1。L, int dk ) { //一趟希爾插入排序 。先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè) “ 增量 ” 的元素組成的）分別進(jìn)行直接插入排序，待整個(gè)序列中的元素基本有序 （增量足夠?。r(shí)，再對全體元素進(jìn)行一次直接插入排序（ 接近最好情況，效率很高 ），因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。 4）表插入排序性能分析 表插入排序的結(jié)果只是求得一個(gè)有序鏈表，則只能對它進(jìn)行順序查找，不能進(jìn)行隨機(jī)查找，為了能實(shí)現(xiàn)有序表的折半查找，尚需對記錄進(jìn)行重新排列。和直接插排序相比，不同之處 僅是以修改2n次指針值代替移動(dòng)記錄 ，排序過程中所需進(jìn)行的關(guān)鍵字間的 比較次數(shù)相同 。 //靜態(tài)鏈表類型 2）待排記錄序列的存儲(chǔ)結(jié)構(gòu) 3）具體做法 首先將靜態(tài)鏈表中數(shù)組下標(biāo)為 “ 1” 的分量（結(jié)點(diǎn)）和表頭結(jié)點(diǎn)構(gòu)成一個(gè)循環(huán)鏈表，然后依次將下標(biāo)為 “ 2”至 “ n”的分量（結(jié)點(diǎn)）按記錄關(guān)鍵字非遞減有序插入到循環(huán)鏈表中。 //0號(hào)單元為表頭結(jié)點(diǎn) int length。 //指針項(xiàng) } SLNode。 define MAXSIZE 100 //靜態(tài)鏈表容量 Typedef struct{ RcdType rc。 插入排序 ? 直接插入排序 ? 折半插入排序 ? 2路插入排序 ? 表插入排序 ? 希爾排序 1）基本思想 通過改變排序過程中采用的存儲(chǔ)結(jié)構(gòu)，減少在排序過程中進(jìn)行 “ 移動(dòng) ” 記錄的操作。 利用靜態(tài)鏈表進(jìn)行排序 ，并在排序完成之后，一次性地調(diào)整各個(gè)記錄相互之間的位置，即將每個(gè)記錄都調(diào)整到它們所應(yīng)該在的位置上。 //記錄項(xiàng) int next。 //表結(jié)點(diǎn)類型 Typedef struct{ SLNode r[MAXSIZE+1]。 //鏈表當(dāng)前長度 } SLinkListType。 初始 狀態(tài) 0 1 2 3 4 5 6 7 8 MAXINT 49 38 65 97 76 13 27 49 1 0 i=3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1