理解和掌握20xx06fx-資料下載頁
2025-09-25 18:52本頁面
【正文】 08 16 21 25* 25 49 3 08 16 21 25* 25 49 1 08 16 21 25* 25 49希爾排序的過程 ? 快速排序 （分區(qū)排序） ? 快速排序的算法。 ? 快速排序的實例。 ? 快速排序是不穩(wěn)定的排序方法。 ? 就平均計算時間而言 , 快速排序是所有內(nèi)排序方法中最好的一個 ,每趟等分排序區(qū)間 , 計算時間 O(nlog2n) 。 ? 當(dāng)初始排列已經(jīng)有序時 , 速度最慢 ,數(shù)據(jù)比較達 n(n1)/2 次。 i = 1 ( 0 ) ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) p i v o t 初始 [ 21 2 5 4 9 2 5 * 16 0 8 ] 2 1 ↑p ↑i ↑i ↑i ↑i 循環(huán) 4 [ 21 16 4 9 2 5 * 25 08 ] 2 5 ? 1 6 ↑p ↑i ↑i 循環(huán) 5 [ 21 1 6 08 2 5 * 2 5 49 ] 4 9 ? 0 8 ↑p ↑i 出循環(huán) [ 08 1 6 ] 21 [ 2 5 * 2 5 4 9 ] 2 1 ? 08? 直接選擇排序 ? 直接選擇排序的算法。 ? 直接選擇排序的實例。 ? 直接選擇排序是不穩(wěn)定的排序方法。 ? 數(shù)據(jù)比較次數(shù)不受初始排列影響 = n(n1)/2。 ? 數(shù)據(jù)移動次數(shù)受初始排列影響 , 最好 0 次，最壞 3(n1) 次。 ? 歸并排序 ? 歸并排序的實例（不要算法）。 ? 歸并排序是穩(wěn)定的排序方法。 ? 歸并趟數(shù) = ?log2(n+1)? , n 是待排序數(shù)據(jù)對象個數(shù)。 ? 每趟 數(shù)據(jù)比較次數(shù)受初始排列影響 , 最好（有序） ? n/2, 最壞 = n1。 ? 數(shù)據(jù)移動次數(shù)不受初始排列影響 , O(nlog2n) 次（表之間傳送）。 第十章 索引與散列 ? 理解和掌握 ? B 樹 ? 散列 ? 需要掌握的知識點 ? B 樹 ? m階 B樹 是 平衡 m路搜索樹 。 ? m階 B樹 所有失敗結(jié)點在同一層。故平衡 m路搜索樹 不一定是 m階 B樹 。 ? m階 B樹 的非失敗結(jié)點最多包含 m1 個關(guān)鍵碼 , 最少 ?m/2? 1 個關(guān)鍵碼。 ? m階 B樹 高度不超過 (含失敗結(jié)點 )： h ? log ?m / 2? ( (n+1)/2 )+1 ? 散列 ? 散列函數(shù)：除留余數(shù)法。 ? 解決沖突的閉散列法（線性探查）。 ? 解決沖突的開散列法。 ? 除留余數(shù)法注意除數(shù)的選擇：質(zhì)數(shù)。 ? 除留余數(shù)法優(yōu)于其他散列函數(shù)。 ? 開散列法優(yōu)于閉散列法。 ? 閉散列情形不能真正做表項的物理刪除 , 否則會中斷其他表項的查找。 ? 閉散列法 ? 線性探查的探查序列 ? 搜索成功的平均探查次數(shù) ? 搜索不成功的平均探查次數(shù) ? 探查序列 H0 = Hash(key) Hi = (H0 + i) % m, i = 1,2,…, m 1 ? 搜索成功的平均探查次數(shù) = 每個已有表項找到它的比較次數(shù)的平均值 ? 搜索不成功的平均探查次數(shù) = 散列函數(shù)可能算出的散列地址上插入新表項時找到空位的比較次數(shù)的平均值 ? 線性探查法容易產(chǎn)生“堆積” ? 閉散列法 ? 1, 開散列法 ? 可大于 1 ? 平均搜索長度取決于裝填因子 ? ? 平均搜索長度與裝填因子之間關(guān)系 處理沖突 平均搜索長度 A S L 的方法 搜索成功 S n 搜索不成功 ( 登入新記錄 ) U n 線性探查法 ?????????????? ?????????????????)(
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1