26排序問(wèn)題和插入排序(45頁(yè))-預(yù)覽頁(yè)
【正文】 排序方法 插入排序： 將無(wú)序子序列中的 一個(gè)或幾個(gè)記錄“ 插入 ”到有序序列中，從而增加記錄的有序子序列的長(zhǎng)度。 基數(shù)排序： 是一種借助多關(guān)鍵字排序的思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法。 // 其它數(shù)據(jù)項(xiàng) } RcdType。 // 順序表類型 插入排序 一趟插入排序的基本思想： 有序序列 R[1..i1] R[i] 無(wú)序序列 R[i..n] 有序序列 R[1..i] 無(wú)序序列 R[i+1..n] 插入排序 一趟插入排序的實(shí)現(xiàn)步驟： 3． 將 R[i] 插入 (復(fù)制 )到 R[j+1]的位置上。 R[0].keyR[j].key。 j) R[j+1] = R[j] 上述循環(huán)結(jié)束后可以直接進(jìn)行“插入” 直接插入排序 void InsertionSort ( SqList amp。 ++i )//把第 2n的對(duì)象插入 if ([i].key [i1].key) { } } // InsertSort [0] = [i]。 // 記錄后移 [j+1] = [0]。L ) { } // BInsertSort 在 [1..i1]中折半查找插入位置； for ( i=2。 j=high+1。 high = i1。 // 插入點(diǎn)在高半?yún)^(qū) 折半插入排序 0 1 2 3 4 5 6 7 8 9 10 14 36 49 52 80 58 61 23 97 75 58 low i high 待排序元素的插入位置 low mid mid low mid high 折半插入排序性能分析 1） 折半插入排序 所需附加存儲(chǔ)空間和 直接插入排序 相同，從時(shí)間上來(lái)看，折半插入排序 減少了關(guān)鍵字的比較次數(shù) ，但是 移動(dòng)次數(shù)不變 。 是 shell在 1959年提出的 。 例如：將 n 個(gè)記錄分成 d 個(gè)子序列： { R[1]， R[1+d]， R[1+2d]， … ， R[1+kd] } { R[2]， R[2+d]， R[2+2d]， … ， R[2+kd] } … { R[d]， R[2d]， R[3d]， … ， R[kd]， R[(k+1)d] } 其中， d 稱為增量，它的值在排序過(guò)程中從大到小逐漸縮小 ，直至 最后一趟 排序減為 1。 ++i ) if ( [i].key [idk].key) { [0] = [i]。([0].key[j].key)。L, int dlta[], int t) { // 增量為 dlta[]的希爾排序 for (k=0。 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,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1