26排序問題和插入排序(45頁)(存儲(chǔ)版)
【正文】 思想：對(duì)待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。 // 暫存在 R[0] for (j=idk。 kt。 不是穩(wěn)定的算法 希爾排序 用希爾排序?qū)?shù)組 {98， 36， 9， 0， 47，23， 1， 8， 10， 7}進(jìn)行排序，給出的步長(zhǎng)依次是 5， 3， 1，寫出前兩趟趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序 小結(jié)和作業(yè) 本次課主要介紹了： 1． 定義 2． 分類 3． 穩(wěn)定性和存儲(chǔ)方式 4． 排序算法的評(píng)價(jià) 小結(jié)和作業(yè) 本次課主要介紹了： 1． 基本思想 2． 實(shí)例模擬 3． 算法描述 4． 算法的復(fù)雜度 作業(yè)： (1， 2)， （思考） 。 // 插入 } // if } // ShellInsert 希爾排序 void ShellSort (SqList amp。 i=n。 希爾排序 又稱為縮小增量排序。 // 插入 折半插入排序 low = 1。 折半插入排序 void BiInsertionSort ( SqList amp。 i=。 // 設(shè)置“哨兵” 循環(huán)結(jié)束表明 R[i]的插入位置為 j +1 for (j=i1。 // 關(guān)鍵字項(xiàng) InfoType otherinfo。 內(nèi)部排序方法的分類 內(nèi)部排序的過程是一個(gè) 逐步擴(kuò)大 記錄的 有序序列長(zhǎng)度 的過程。排序問題和插入排序 排序問題 插入排序 小結(jié)和作業(yè) 排序的定義 內(nèi)部排序和外部排序 內(nèi)部排序方法的分類 排序問題 排序的定義 排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組 “ 無序 ” 的記錄序列調(diào)整為 “ 按關(guān)鍵字有序 ” 的記錄序列。 ： 參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程 不可能在內(nèi)存中完成。 // 關(guān)鍵字類型為整數(shù)類型 待排記錄的數(shù)據(jù)類型定義如下 : typedef struct { KeyType key。 利用 “順序查找” 實(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]。 for ( i=2。 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,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1