26排序問(wèn)題和插入排序(45頁(yè))(編輯修改稿)
2025-06-08 13:19 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 0 1 2 3 4 5 6 7 i=3: 49 65 直接插入排序 49 65 97 76 13 27 38 0 1 2 3 4 5 6 7 49 65 97 76 13 27 38 0 1 2 3 4 5 6 7 i=4: 49 65 97 49 65 97 76 13 27 38 0 1 2 3 4 5 6 7 76 i=5: 76 97 直接插入排序 49 65 76 97 13 27 38 0 1 2 3 4 5 6 7 49 65 76 97 13 27 38 0 1 2 3 4 5 6 7 13 i=6: 49 38 65 76 97 13 38 49 65 76 97 27 13 0 1 2 3 4 5 6 7 27 i=7: 49 38 65 76 97 27 直接插入排序性能分析 實(shí)現(xiàn)內(nèi)部排序的基本操作有兩個(gè)： 2）“移動(dòng)”記錄。 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) 用直接插入排序法對(duì)下面四個(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)?折半插入排序 。 折半插入排序 void BiInsertionSort ( SqList amp。L ) { } // BInsertSort 在 [1..i1]中折半查找插入位置； for
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1