26排序問題和插入排序(45頁)(編輯修改稿)
2025-06-08 13:19 本頁面
【文章內(nèi)容簡介】 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 直接插入排序性能分析 實現(xiàn)內(nèi)部排序的基本操作有兩個： 2）“移動”記錄。 1）“比較”序列中兩個關(guān)鍵字的大??； 直接插入排序性能分析 比較次數(shù) 移動次數(shù) 最好情況 最壞情況 211nin????0 2( 4 ) ( 1 )( 1 )2ninni??????關(guān)鍵字在記錄序列中順序有序 關(guān)鍵字在記錄序列中逆序有序 O(n2) 時間復雜度： 穩(wěn)定性： 是一種 穩(wěn)定 的排序方法 2( 4 ) ( 1 )( 1 )2ninni??????直接插入排序 練習 直接插入排序在最好情況下的時間復雜度為（） A. O(logn) B. O(n) C. O(nlogn) D. O(n2) 用直接插入排序法對下面四個序列進行排序（由小到大），元素比較次數(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] 是一個按關(guān)鍵字有序的有序列，則可以 利用 折半查找 實現(xiàn)“在 R[1..i1]中 查找 R[i]的 插入位置 ” ，如此實現(xiàn)的插入排序為 折半插入排序 。 折半插入排序 void BiInsertionSort ( SqList amp。L ) { } // BInsertSort 在 [1..i1]中折半查找插入位置； for
教學課件相關(guān)推薦
鄂ICP備17016276號-1