26排序問題和插入排序(45頁)-wenkub.com
2025-04-19 13:19 本頁面
【正文】 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，序列中的值沒有除 1以外的公因子。 ++t) ShellInsert(L, dlta[k])。 // 記錄后移，查找插入位置 [j+dk] = [0]。 j0amp。L, int dk ) { for ( i=dk+1。 所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。 3）折半插入排序是一個(gè) 穩(wěn)定 的排序方法。 // 折半 if ([0].key [m].key) high = m1。 // 記錄后移 [high+1] = [0]。 ++i ) { } // for [0] = [i]。 1）“比較”序列中兩個(gè)關(guān)鍵字的大?。? 直接插入排序性能分析 比較次數(shù) 移動(dòng)次數(shù) 最好情況 最壞情況 211nin????0 2( 4 ) ( 1 )( 1 )2ninni??????關(guān)鍵字在記錄序列中順序有序 關(guān)鍵字在記錄序列中逆序有序 O(n2) 時(shí)間復(fù)雜度： 穩(wěn)定性： 是一種 穩(wěn)定 的排序方法 2( 4 ) ( 1 )( 1 )2ninni??????直接插入排序 練習(xí) 直接插入排序在最好情況下的時(shí)間復(fù)雜度為（） A. O(logn) B. O(n) C. O(nlogn) D. O(n2) 用直接插入排序法對下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是（） A. 94, 32, 40, 90, 80, 46, 21, 69 B. 32, 40, 21, 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] 是一個(gè)按關(guān)鍵字有序的有序列，則可以 利用 折半查找 實(shí)現(xiàn)“在 R[1..i1]中 查找 R[i]的 插入位置 ” ，如此實(shí)現(xiàn)的插入排序?yàn)?折半插入排序 。 [0].key [j].key。 for ( i=2。 // 從后往前找 直接插入排序 對于在查找過程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)； for (j=i1。 利用 “順序查找” 實(shí)現(xiàn)“在 R[1..i1]中查找 R[i]的插入位置” 直接插入排序 算法實(shí)現(xiàn)要點(diǎn)： 從 R[i1]起向前進(jìn)行順序查找， 監(jiān)視哨設(shè)置在 R[0]； R[0] j R[i] j= i1 插入位置 直接插入排序 算法實(shí)現(xiàn)要點(diǎn)： R[0] = R[i]。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1