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