26排序問題和插入排序(45頁)-文庫吧在線文庫
【正文】 46, 69, 94, 90, 80 C. 21, 32, 46, 40, 80, 69, 90, 94 D. 90, 69, 80, 46, 21, 32, 94, 40 折半插入排序 如果 R[1..i1] 是一個按關(guān)鍵字有序的有序列，則可以 利用 折半查找 實現(xiàn)“在 R[1..i1]中 查找 R[i]的 插入位置 ” ，如此實現(xiàn)的插入排序為 折半插入排序 。 // 記錄后移 [high+1] = [0]。 3）折半插入排序是一個 穩(wěn)定 的排序方法。L, int dk ) { for ( i=dk+1。 // 記錄后移，查找插入位置 [j+dk] = [0]。 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個值必須是 1，序列中的值沒有除 1以外的公因子。 ++t) ShellInsert(L, dlta[k])。 j0amp。 所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。 // 折半 if ([0].key [m].key) high = m1。 ++i ) { } // for [0] = [i]。 [0].key [j].key。 // 從后往前找 直接插入排序 對于在查找過程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時實現(xiàn)記錄向后移動； for (j=i1。 // r[0]閑置 int length。 選擇排序： 從記錄的無序子序列中 “ 選擇 ” 關(guān)鍵字 最小或最大 的記錄，并將它加入到 有序子序列中 ，以此方法增加記錄的有序子序列的長度。也稱為 排序碼 。 排序的定義 排序方法的穩(wěn)定性 : 如果在對象序列中有兩 個對象 r[i]和 r[j], 它們的排序碼 k[i] = k[j] , 且在排序之前 , 對象 r[i]排在 r[j]前面。 各種排序方法的定義 歸并排序： 通過 “ 歸并 ” 兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。 // 順序表長度 } SqList。 R[0].keyR[j].key。 j ) [j+1] = [j]。 // 將 [i] 暫存到 [0] for ( j=i1。 // 插入點在低半?yún)^(qū) else low = m+1。 希爾排序 將記錄序列分成若干子序列，分別對每個子序列進行插入排序。amp。 //一趟增量為 dlta[k]的插入排序 } // ShellSort 希爾排序 算法描述舉例 int d[]={5,3,1}。 1 2 3 4 5 6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1