【正文】 （ I） 168 歸并排序 merge子圖（ II） 169 排序算法的分析 ? 冒泡排序顯然最容易實現(xiàn)對已經(jīng)存在的無序線形表進行排序，所以最為最常見； ? 插入排序?qū)τ陔S機產(chǎn)生的無序數(shù)據(jù)，可以實現(xiàn)實時排序； ? 歸并排序的前提是存在兩個以上已經(jīng)排序的線形表； ? 桶排序則適用于可以進行分類的數(shù)據(jù)排序； ? 快速排序則是最能體現(xiàn)時間復(fù)雜性優(yōu)化的排序算法，但要關(guān)注其在不同的實現(xiàn)環(huán)境中，可能因空間復(fù)雜性所帶來的問題 170 排序算法的分析 穩(wěn)定性分類 算法名稱 時間復(fù)雜性 空間復(fù)雜性 穩(wěn)定排序 冒泡排序 O(n^2) O(1) 插入排序 O(n^2) O(1) 桶排序 O(n) O(k) 空間 合并排序 O(nlogn) O(n) 空間 不穩(wěn)定排序 快速排序 O(nlogn) 最壞 O(n^2) 穩(wěn)定性分類 算法名稱 時間復(fù)雜性 空間復(fù)雜性 171 End of ch51 172 第 5章 B 查找 《可視化計算》 查找 ? 查找算法和排序算法有密切的聯(lián)系，因為許多查找算法依賴于要查找的數(shù)據(jù)集的有序程度 ? 基本的查找算法有以下 4種： ? 順序查找； ? 比較查找也稱二分查找； ? 基數(shù)查找也稱分塊查找； ? 哈希查找 174 順序查找 ? 順序查找過程： ? 通常從表中的第一個（或最后一個）記錄開始，將記錄的關(guān)鍵字與給定值逐個進行比較 ? 當(dāng)某個記錄的關(guān)鍵字與給定值相等時，即找到所查的記錄，查找成功； ? 反之，若查到最后一個記錄，其關(guān)鍵字和給定值的比較都不相等，則表明表中沒有所查的記錄，查找失敗。 175 順序查找 的算法設(shè)計 ? 由于順序查找的數(shù)據(jù)表，無需將節(jié)點實現(xiàn)排序，所以可以直接使用隨機數(shù)產(chǎn)生一張線形表，進行查找的實驗 176 二分查找 ? 基本思想 ： ? 將 n個元素分成個數(shù)大致相同的兩半，取 a[n/2]與欲查找的 x作比較，如果 x=a[n/2]則找到 x，算法終止 ? 如果 xa[n/2]，則需要在數(shù)組 a的右半部繼續(xù)搜索 ? 直至找到 x為止或得出關(guān)鍵字不存在的結(jié)論 ? 算法實現(xiàn)的前提 ? ? 177 178 二分查找 的算法說明 ? 子程序先將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功； ? 否則利用中間位置記錄將表分成前、后兩個子表 ? 如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進一步查找前一子表 ? 否則將繼續(xù)查找后一子表 ? 重復(fù)以上過程，直至找到滿足條件的記錄，或者根本查不到子表，此時查找失敗 179 二分查找 的算法分析 ? +折半查找法每執(zhí)行一次，都可以將查找空間減少一半，是計算機科學(xué)中分治思想的完美體現(xiàn) ? 其缺點是要求待查表為有序表，而有序表的特點則是插入刪除困難 ? 因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的 有序列表 180 分塊查找 ? 使用撲克牌計算 24點 ? 該算法是從數(shù)字為 1~10的撲克牌中任意抽出四張，運用加、減、乘、除，在運算中可以引入括號，每張牌只能用一次，使其計算結(jié)果為 24 ? 在廣泛的社會實踐的基礎(chǔ)上可以分析和認(rèn)識到： ? 在一副牌（只保留數(shù)字點數(shù)的 40張）中任意抽取 4張，總共有 715種不同組合形式，其中有 149種組合的運算結(jié)果不可能為 24 181 不可計算 24的牌組 (149個 ) 182 不可計算的牌組如何確定？ ? 計算搜索開始前，先檢查某個特定牌組的計算可能性呢？ ? 如果肯定得不到 24的計算結(jié)果（例如， 1，1， 1， 1和 10， 10， 10， 10），那么就可以馬上重新發(fā)牌，開始新一輪計算 ? 可以使用查表的方式來解決！ 183 問題 ? 每次查閱這張表也不是一個簡單的過程，因為該表列出的關(guān)鍵字是使用字符串實現(xiàn)的，盡管字符串也可以轉(zhuǎn)換成數(shù)字進行排序，但顯然會增加查找過程的計算工作量 ? 能否設(shè)計一個算法，不用轉(zhuǎn)換關(guān)鍵值，又可以減少順序查找的掃描工作量？ ? 可以考慮采用 分塊查找算法 ，該算法又稱索引順序查找 ，它是順序查找的一種改進方法 184 分塊查詢的基本思想 ? 將 n個數(shù)據(jù)元素 按塊有序 劃分為 m塊 （ m ≤ n） ? 每一塊中的節(jié)點不必有序，但塊與塊之間必須 按塊有序 ； ? 即第 1塊中任一元素的關(guān)鍵字都必須小于第 2塊中任一元素的關(guān)鍵字； ? 而第 2塊中任一元素又都必須小于第 3塊中的任一元素， ? 185 分塊查找的實現(xiàn) ? 不可計算牌組保存在（以文本格式）文件中 ? 從文件讀入后，產(chǎn)生一個索引數(shù)組 ? 保存各塊的起始元素下標(biāo) 186 分塊算法設(shè)計的說明 ? 主要子圖 ? Main：主流程控制；輸入 /輸出 ? Input_list_stringc：從文件讀入 149個牌組 ? Indexing：建立分塊索引表 ? Random_number：產(chǎn)生測試牌組 a[] ? Sort：將測試牌組 a[]排序 ? Setsample:將測試牌組 a[]轉(zhuǎn)成測試字符串 ? Block_search_test:進行分塊查找 187 分塊查詢 ? Main子圖 188 分塊查詢 ? 主要數(shù)據(jù)結(jié)構(gòu) : ? Str_list[]: 保存文件讀入的149個牌組，字符串 ? A[]：保存隨機產(chǎn)生的 4張牌（1~10），數(shù)值 ? In_key:保存排序完成的牌組樣本，字符串 ? Index[， ]：保存分塊索引表， 189 分塊查詢 ? Set_sample子圖 190 分塊查詢 ? Indexing子圖 191 分塊算法設(shè)計的分析 ? 分塊查找的第一部分是進行索引表的查詢 ? 一般來說，索引表長度在 10以內(nèi)，就可以使用順序查找，否則使用二分查找 ? 為了簡化算法，本例將 149組 數(shù)據(jù)只劃分了9個塊，以 10開始的牌組只有一個，這里將其與 9開始的牌組合并了 ? 24點牌組的不可計算 比 為 149/715，將查詢初值 ok賦值為 true，可以減少賦值運算的次數(shù) 192 分塊算法的運行說明 ? 由于采用隨機數(shù)產(chǎn)生測試牌組，所以測試無需輸入樣本，只要回答， y/n即可 ? 需要自行輸入樣本，可以自行修改樣例算法，再進行測試 193 分塊查找的時間復(fù)雜度 ? 分塊查找的時間復(fù)雜度： O（索引表查找 +塊內(nèi)查找） ? O（索引表二分查找 +塊內(nèi)順序查找） ? O(log2 B) + (M+1） /2 ? O（索引表順序查找 +塊內(nèi)順序查找） ? O（ (B+1） /2 + (M+1） /2） ? 一般描述： O（ ） ? 分析： ? 實際應(yīng)用中不一定分成大小相等的塊，可按表的特征分塊（如本例所設(shè)計） ? 提高了順序查找的效率，但付出了空間的代價（索引表） 194 哈希查找 ? 哈希是 hash的音譯，意為“雜湊”，也稱散列 ? 哈希表是一種重要的存儲方式，哈希查找技術(shù)是一種按照關(guān)鍵字編址的檢索方法 ? 哈希查找不同于前面的幾種查找方法，它是通過對記錄的關(guān)鍵字值進行某種運算，直接求出記錄文件的地址 ? 是 關(guān)鍵字到地址 的直接轉(zhuǎn)換方法，而不需要反復(fù)比較 ，所以計算復(fù)雜性為常數(shù)階： O（ 1） 195 哈希查找的實現(xiàn)過程 ? 仍以 24點不可計算作為基本查找的數(shù)據(jù)集 ? 由于哈希查找需要對牌組內(nèi)的牌面進行計算 ? 注意這一點與分塊查找不同 ? 每個牌組內(nèi)的每張牌面，都 必須轉(zhuǎn)變成可以計算的數(shù)字 ? 需要設(shè)計哈希函數(shù)并構(gòu)建哈希表 196 哈希表查找方法的基本思想 ? 如果在記錄的存儲位置與它的關(guān)鍵字之間建立一個確定的關(guān)系 H（） ? 使每個關(guān)鍵字和一個唯一的存儲位置相對應(yīng) ? 在查找時，只需要根據(jù)對應(yīng)關(guān)系計算出給定的關(guān)鍵字值 k對應(yīng)的值 H(k)，就可以得到記錄的存儲位置 ? 在使用 哈希方法解決 24點不可計算牌組 時，就是將牌面數(shù)字計算后查表，可以查到為不可計算；不可查到就是可以計算 197 哈希表的構(gòu)建 ? 哈希函數(shù)（ hash function）， 記錄的關(guān)鍵字值與記錄的存儲位置的對應(yīng)關(guān)系 H稱為哈希函數(shù)， H(k)的結(jié)果被稱為 哈希地址 ? 哈希表（ hash table） ，是根據(jù)哈希函數(shù)建立的表，以記錄的關(guān)鍵字值為自變量，根據(jù)哈希函數(shù)，計算出對應(yīng)的哈希地址，并在此 存儲該記錄的內(nèi)容 198 哈希沖突與解決 ? 沖突（ collision） ，不同的關(guān)鍵字值其哈希函數(shù)計算的哈希地址相同，具有相同函數(shù)值的關(guān)鍵字值稱為 同義詞（ synonym） ? 本例中處理 同義詞 沖突的方法是 拉鏈法 ，當(dāng)發(fā)生沖突時，在沖突位置的二維數(shù)組行上尋找存放記錄的空閑單元 199 24點算法的不可計算案例哈希 ? 設(shè)定哈希表的長度為 149， H關(guān)系為： ? H(key)=key mod 149 + 1 ? Key的獲取原則為： ? 所有 10牌面模除 7余 3，再參與其他牌面的計算，例如， 10 10 10 10等同 3 3 3 3 ? 去掉 10以后的所有牌面數(shù)：key=d1*1000+d2*100+d3*10+d4 ? H(Key)=3333 mod 149+1=56 200 計算所得的哈希表（局部） 不可計算牌組直接轉(zhuǎn)換成為字符串； 按哈希規(guī)則尋址保存在文件記錄中 201 構(gòu)建哈希表的一些要點 ? 可以采用 149行， N列的二數(shù)組保存哈希表（也就是將同義詞的牌組，按計算順序在一行中排放） ? 在運行后，發(fā)現(xiàn)最大的沖突數(shù)為 3，因此該算法的實際哈希表為 149*3=447個數(shù)據(jù)單元 ? 在本例構(gòu)建的哈希表（ hash_1[]）的初始化過程中，所有數(shù)組元素皆為數(shù)值 0，在保存牌組時，首先要 檢測當(dāng)前數(shù)組元素的數(shù)據(jù)類型 ? 如果不是數(shù)值類型，則說明已經(jīng)填入了數(shù)據(jù)，需要尋找 鄰接的 屬于數(shù)值類型的元素再寫入 202 哈希表的應(yīng)用 ? 在應(yīng)用時，先載入已準(zhǔn)備的哈希表 ? 隨機生成 24點牌組，應(yīng)用哈希規(guī)則得到哈希表的地址 ? 進行查表操作，可以查到，則為不可計算牌組；不可查到，則為可計算牌組 ? 查找的效率在 1到 3次之間，時間復(fù)雜度為： O（ 1） 203 小結(jié)與回顧 ? 查找策略則與數(shù)據(jù)的排序與否，數(shù)據(jù)自身的屬性有重大關(guān)系。 ? 順序查找針對未排序數(shù)據(jù)， ? 二分查找針對已排序數(shù)據(jù)， ? 分塊查找針對按塊有序、塊內(nèi)無序的數(shù)據(jù) ? 而最能體現(xiàn)計算機科學(xué)精髓的查找方法則是哈希查找，哈希查找是通過計算數(shù)據(jù)元素的存儲地址進行查找的算法 204