資源簡介

(共91張PPT)
第6章 查找與排序
查找
排序
查找
排序
6.2
6.1
點擊查看本小節知識架構
點擊查看本小節知識架構
學習目標
掌握
掌握
掌握
掌握
掌握常用的查找算法
1
掌握排序算法的代碼編寫方法
4
2
掌握常用的排序算法
3
掌握查找算法的代碼編寫方法
本章將主要介紹算法中的常用操作——查找與排序。查找與排序作為數據處理的基本操作，是學習編程必須掌握的。查找是在給定的數據集合（表）中搜索指定的數據元素。排序是將數據集合中的各個數據元素按照指定的順序進行排列。查找與排序的算法很多，根據數據集合的不同特點使用不同的查找與排序算法，可以節省空間與時間，提高程序效率。本章將重點圍繞查找與排序算法的原理與代碼實現進行介紹。
6.1 查找
6.1.1
順序查找
返回目錄
6.1.2
折半查找
6.1.3
分塊查找
6.1.4
哈希查找
6.1 查找
設記錄表 L=(R 1 ,R 2, …R n )，其中 R i (1≤i≤n)為記錄，對給定的某個值 k，在表 L 中確定 key=k 的記錄的過程，稱為查找。若表 L 中存在一個記錄 R i的 key 等于 k，記為 R i .key=k，則查找成功，返回該記錄在表 L 中的序號 i （或R i 的地址），否則（查找失敗）返回 0（或 NULL）。
查找算法有順序查找、折半查找、分塊查找、哈希查找等。查找算法會影響計算機的使用效率，應根據應用場合選擇相應的查找算法。
6.1.1 順序查找
順序查找（Sequential Search）又可以稱為線性查找，是最基本的查找技術。順序查找的基本原理是從數據集合中的第一個（或最后一個）數據元素開始，逐個與給定值進行對比。如果某個數據元素與給定值相同，則查找成功。如果查找到最后一個（或第一個）數據元素，都與給定值不同，則查找失敗。
順序查找算法比較簡單，以整型數據為例，代碼如例所示。
6.1.1 順序查找
6.1.1 順序查找
例采用循環的方式遍歷整個數據集合（數組），與指定值進行對比，相等則查找成功。程序運行結果如下。
運行結果中，輸出指定值4，可見查找成功。
6.1.2 折半查找
當數據集合中的數據元素無序排列時，只能采用順序查找，而如果這個數據集合中的數據元素是有序的，則可以采用折半查找來提高查找效率。
折半查找（Binary Search）又稱為二分查找。折半查找的基本原理是在有序的表中取中間的數據作為比較對象。如果查找的值與中間的值相等，則查找成功；如果查找的值小于中間的值，則到有序表的左半區繼續查找；如果查找的值大于中間的值，則到有序表的右半區繼續查找。不斷重復上述步驟，直到查找成功，如圖所示。
6.1.2 折半查找
在折半查找的過程中，查找范圍不斷變化。每一次查找后，查找范圍都會減小為原來的一半。代碼參考教材6.1.2節。
例每一次查找數據前，都需要尋找當前有序表的中間值，并以此作為判斷標準，與給定值進行對比。如果給定值小于中間值，則將查找范圍減少，下一次查找有序表的左半區；反之則查找右半區。如果給定值與中間值相等，則查找成功，輸出該中間值的下標。程序運行結果如下。
運行結果中，輸入給定值5，顯示查找失敗，說明該值不在有序表（數組）中。輸入給定值15，返回該值在有序表中的下標5。
由上述分析可知，折半查找的時間復雜度為O(log 2 n)，相較于順序查找（時間復雜度為O(n)），折半查找更加高效。需要注意的是，折半查找的前提是數據集合必須是有序的。
6.1.3 分塊查找
分塊查找（Block Search）又稱為索引順序查找，是介于順序查找與折半查找之間的查找算法，也是順序查找算法的一種改進算法。
分塊查找類似于從書籍中查找資料。假設讀者需要從一本書中查找資料，一般的做法是先從目錄開始，找到資料所在章節的起始頁面，然后從該起始頁向后尋找。這種做法明顯要比從書的第一頁向后查找快很多。因此，書籍在編輯時，都會將所有的內容按照一定的規則分成若干塊（章），每一塊再分為若干個小塊（節），并設置它們的位置（頁），形成一個目錄，通過這個目錄即可實現快速查找。這個目錄就是索引表，這種查找方式就是分塊查找。
分塊查找需要將數據集合分成若干個塊，并且這些塊滿足兩個條件。
（1）塊內無序，即每一塊中的數據不要求有序。
（2）塊間有序，即塊與塊之間是有序的。后一個塊中的各個數據元素都比前一個塊中的任何數據元素大。例如，第一個塊中的數據元素都小于 30，那么第二個塊中的數據元素都必須大于等于 30。
6.1.3 分塊查找
分塊查找算法的核心是設置一張索引表，索引表中的每一項（索引項）對應一個數據塊。索引項由以下 3 部分組成。
（1）數據塊中最大的數據元素。
（2）數據塊中數據元素的個數。
（3）指向數據塊中首元素的指針（塊首指針），即首元素的地址。
數據塊與索引表的關系如圖所示。
6.1.3 分塊查找
分塊查找算法需要兩步完成，具體如下。
（1）在索引表中查找數據所在的塊，由于數據塊之間是有序的，可以利用折半查找很快得到結果。例如，在圖 6.2 中查找數據 43 所在的塊，由于第 2 個數據塊的最大值為 27，第 3 個數據塊的最大值為 56，很容易判定數據 43 在第 3 個數據塊中。
（2）根據索引表中的塊首指針，在對應的數據塊中按照順序查找數據。（數據塊中的數據是無序的，只能采用順序查找。）
分塊查找算法的代碼參考教材6.1.2節。
6.1.3 分塊查找
例使用結構體數組 NodeTable node[18]存儲數據集合，IdxTable idx[3]為索引表，同樣為結構
體數組，數據元素為 3 個。因此，測試使用的數據集合分為 3 個數據塊，塊長為 6。子函數 BlkSearch()
實現分塊查找算法，其中調用函數 BiSearch()（折半查找算法）先查找數據所在的數據塊，然后使用順序查找的方式在數據塊中查找具體的數據。程序運行結果如下。
輸入待查找數據 48，由例的第 58 行代碼可知，48 在數組中的下標值為 11，程序輸出結果同樣為 11，測試成功。
6.1.3 分塊查找
例中，BiSearch()函數用來確定數據所在的塊，具體分析如下。
（1）假設數據集合分為 10 個數據塊（每個數據塊中的數據元素不確定），如圖所示。
（2）假設當前需要查找的數據 key 在數據塊 4 中且不是塊中的最大值，結合例中的函數BiSearch()可知，第一次執行 while 循環時，low 的值為 0，high 的值為 9，因此 mid 的值為 4。分析可知，key < idx[4].key，即待查找數據小于數據塊 4 中的最大值，需要執行代碼 high=mid-1，high 的值變為 3，如圖所示。
6.1.3 分塊查找
（3）第一次循環后，high 的值變為 3，low 的值不變。再次執行循環，mid 的值為 1。分析可知，key > idx[1].key，即待查找數據大于數據塊 1 中的最大值，需要執行代碼 low=mid+1，low 的值變為2，如圖所示。
（4）第二次循環后，high 的值為 3，low 的值變為 2。再次執行循環，mid 的值為 2。分析可知，key > idx[2].key，即待查找數據大于數據塊 2 中的最大值，需要執行代碼 low=mid+1，low 的值變為3，如圖所示。
6.1.3 分塊查找
（5）第三次循環后，high 的值為 3，low 的值變為 3。再次執行循環，mid 的值為 3。分析可知，key > idx[3].key，即待查找數據大于數據塊 3 中的最大值，需要執行代碼 low=mid+1，low 的值變為4，如圖所示。
（6）第四次循環后，low 的值為 4，high 的值為 3。由于 low 的值大于 high，循環結束。由圖 6.7 可知，需要查找的數據在第 high+1 個數據塊中。
6.1.4 哈希查找
1．哈希函數的構造方法
哈希查找（Hash Search）算法是通過計算數據元素的存儲地址來進行查找的一種算法。算法的原理是查找時通過給定值 k 以及對應關系 f，便可以找到 k 值所對應的哈希地址 f(k)（不需要比較直接獲得查找目標）。這種對應關系 f 就是哈希函數，通過這個思想建立的表稱為哈希表。
哈希函數的構造方法有很多，具體如下。
（1）直接定址法。取關鍵字或關鍵字的某個線性函數值作為哈希地址，即 H(key)=key 或 H(key)=a×key+b（a,b 為常數）。
舉例：某公司統計 25～60 歲的人數，以年齡作為關鍵字，哈希函數取關鍵字自身，假設需要知道年齡為 25 歲的人的數量，則直接查表中的第 1 項即可。
6.1.4 哈希查找
（2）數字分析法。取關鍵字中某些取值較均勻的數字位作為哈希地址。當關鍵字的位數很多時，可以通過對關鍵字的各位進行分析，去掉分布不均勻的位。這種方法只適合于所有關鍵字已知的情況。通過分析分布情況將關鍵字取值區間轉化為一個較小的關鍵字取值區間。
舉例：列出已知關鍵字中的 8 個關鍵字，如表所示。
6.1.4 哈希查找
由表中的 8 個關鍵字可知，關鍵字從左到右的第 1、2、3、6 位取值比較集中（第 1 位都為6，第 2 位是 1 或 2，第 3 位是 3 或 7，第 6 位是 2、6 或 8），不宜作為哈希地址，剩余的第 4、5、7、8 位取值較均勻，可選取其中的兩位作為哈希地址。假設選取最后兩位作為哈希地址，則這 8 個關鍵字的哈希地址分別為 2、75、28、34、15、38、62、20。
（3）平方取中法。取關鍵字平方后的中間幾位作為哈希地址。
舉例：求關鍵字的平方并選取中間位為作為哈希地址，如表所示。
6.1.4 哈希查找
（4）折疊法。將關鍵字分割成位數相同的幾個部分（最后一部分的位數可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址。這種方法適用于關鍵字位數比較多，且關鍵字中每一位上數字分布大致均勻的情況。
（5）除留余數法。取關鍵字被某個不大于哈希表表長 m 的數 p 除后所得的余數作為哈希地址（p為素數）。
（6）隨機數法。選擇一個隨機函數，取關鍵字的隨機函數值作為其哈希地址，即H(key)=random(key)，其中 random()為隨機函數。該方法適用于關鍵字長度不等的情況。
6.1.4 哈希查找
2．哈希沖突
由于通過哈希函數產生的哈希地址是有限的，而在數據比較多的情況下，經過哈希函數處理后，不同的數據可能會產生相同的哈希地址，這就造成了哈希沖突，如圖所示。
6.1.4 哈希查找
除了構造哈希函數外，哈希算法的另一個關鍵問題就是解決哈希沖突，其方法有很多，具體如下。
（1）開放地址法。開放地址法有 3 種探測方式：線性探測、再平方探測、偽隨機探測。線性探測指的是按順序決定哈希地址時，如果某數據的哈希地址已經存在，則在原來哈希地址的基礎上向后加一個單位，直至不發生哈希沖突。再平方探測指的是按順序決定哈希地址時，如果某數據的哈希地址已經存在，則在原來哈希地址的基礎上先加 1 的平方個單位，若仍然存在則減 1 的平方個單位，之后是 2 的平方，以此類推，直至不發生哈希沖突。偽隨機探測指的是按順序決定哈希地址時，如果某數據的哈希地址已經存在，則通過隨機函數隨機生成一個數，在原來哈希地址的基礎上加上隨機數，直至不發生哈希沖突。
（2）建立公共溢出區。建立公共溢出區存儲所有造成哈希沖突的數據。
（3）再哈希法。對沖突的哈希地址再次進行哈希處理，直至沒有哈希沖突。
（4）鏈地址法。對相同的哈希地址使用鏈表進行連接，使用數組存儲每一個鏈表。
6.1.4 哈希查找
接下來將重點介紹鏈地址法的具體實現。鏈地址法又稱為拉鏈法，其基本的思路是將所有具有相同哈希地址的不同關鍵字連接到同一個單鏈表中。如果選定的哈希表長度為 m，則可將哈希表定義為一個由 m 個頭指針組成的指針數組 T[0…m－1]，所有哈希地址為 i 的數據，均以結點的形式插入以 T[i]為頭指針的單鏈表，如圖所示。
6.1.4 哈希查找
鏈地址法實現哈希查找算法的代碼參考教材6.1.4節。
例中，插入的關鍵字共有 11 個，哈希表的長度為 13，對應 13 個鏈表。哈希函數為給定值
對哈希表長度取余（代碼 28 與 61 行），得到結果為哈希地址（數組下標）。程序查詢的給定值為 68，由插入的關鍵字可知，68 屬于其中的一個關鍵字。程序運行結果如下。
6.1.4 哈希查找
由程序運行結果可知，輸出數據為 13 個鏈表中的所有關鍵字，給定值 68 查找成功。程序構建
的哈希表如圖所示。
圖中，關鍵字共有 11 個，其中 16 與 68 的哈希地址相同，7 與 46 的哈希地址相同。
6.2 排序
6.2.1
排序的概念
返回目錄
6.2.2
直接插入排序
6.2.3
希爾排序
6.2.4
直接選擇排序
6.2 排序
6.2.5
堆排序
返回目錄
6.2.6
冒泡排序
6.2.7
快速排序
6.2.8
歸并排序
6.2 排序
排序（Sort）是將無序的記錄序列調整為有序的序列。對序列進行排序有非常重要的意義，例如，對有序的序列進行折半查找，會提高查找的執行效率。在數據庫和文件庫中建立若干索引文件就會涉及排序的問題。在一些計算機的應用系統中按不同的數據段做若干統計同樣也會涉及排序處理。排序效率的高低，直接影響計算機的工作效率。
6.2.1 排序的概念
排序指的是將無序的記錄按照其中某個（或某些）關鍵字的大小以遞增或遞減的順序排列起來的操作。其確切的定義為：假設有 n 個數據元素的序列(R 1 ,R 2 ,…R n )，其相應關鍵字的序列是(K 1 ,K 2 ,…K n )，要求通過排序找出下標 1,2,…n 的一種排列 P 1 ,P 2, …P n ，使得相應關鍵字滿足非遞減（或非遞增）關系 K p1 ≤K p2 ≤…≤K pn ，從而得到一個按關鍵字有序排列的記錄序列(R p1 ,R p2 …R pn )。
按照排序過程中涉及的存儲器的不同，可以將排序分為內部排序與外部排序。內部排序指的是待排序的記錄數較少，所有的記錄都能存放在內存中進行排序。外部排序指的是待排序的記錄數太多，不可能把所有的記錄存放在內存中，排序過程中必須在內存與外存之間進行數據交換。
6.2.1 排序的概念
按照排序過程中對記錄操作方式的不同，可以將排序分為四大類：插入排序、選擇排序、交換排序、歸并排序。其中，每一類排序都有很多經典的排序算法，如表所示。
6.2.2 直接插入排序
1．直接插入排序概述
直接插入排序（Insertion Sort）是一種簡單直觀的排序算法，其工作原理是先構建有序序列，然后在已排序序列中從后向前掃描，為未排序的數據找到相應位置并將其插入。
直接插入排序算法的具體操作步驟如下所示。
（1）從序列的第一個元素開始，該元素被認定為已排序。
（2）在已排序的元素序列中從后向前掃描，為下一個元素尋找位置。
（3）如果已排序的元素大于新插入的元素，則將已排序元素移動到下一位。
（4）重復步驟（3），直到已排序元素小于或等于新插入的元素。
（5）插入新元素。
（6）重復步驟（2）～（5）。
6.2.2 直接插入排序
接下來通過具體的序列對插入排序算法進行說明。如圖所示，假設有一串未排序的元素。
執行上述算法描述的步驟（1），選擇第一個元素作為已排序的元素，如圖所示。
6.2.2 直接插入排序
執行上述算法描述的步驟（2），選擇下一個元素（元素為 12），在已排序的元素中進行掃描，執行算法描述的步驟（3）、（4）、（5）。由于新插入的元素 12 大于已排序的元素 8，因此無須移動已排序的元素 8。插入元素 12 后的效果如圖所示。
重復算法描述的步驟（2），選擇下一個元素（元素為 65），在已排序的元素中從后向前掃描，執行步驟（3）、（4）、（5）。元素 65 先與元素 12 比較，再與元素 8 比較，新插入的元素 65 大于元素 8與元素 12，無須移動已排序的元素。插入元素 65 后的效果如圖所示。
6.2.2 直接插入排序
重復算法描述的步驟（2），選擇下一個元素（元素為 43），在已排序的元素中從后向前掃描，執行步驟（3）、（4）、（5）。元素 43 小于元素 65，將元素 65 向后移動，即兩個元素位置交換；元素 43大于元素 12，則元素 12 無須移動。插入元素 43 后的效果如圖所示。
重復上述操作，插入元素為 55，執行算法描述的步驟（3）、（4）、（5）。元素 55 小于元素 65，大于元素 43。插入元素 55 后的效果如圖所示。
6.2.2 直接插入排序
重復上述操作，插入元素為 32，執行算法描述的步驟（3）、（4）、（5）。元素 32 小于元素 65、55、43，大于元素 12。插入元素 32 后的效果如圖所示。
重復上述操作，插入最后一個元素 24，執行算法描述的步驟（3）、（4）、（5）。元素 24 小于元素65、55、43、32，大于元素 12。插入元素 24 后的效果如圖所示。
6.2.2 直接插入排序
元素 24 插入完成后，整個排序過程結束。如圖所示，新序列為遞增序列。由上述分析可知，插入排序最壞的情況是序列是逆序的，最好的情況是序列是順序的。例如，圖中最后形成的序列是遞增的，如果原始序列呈遞減狀態，則排序過程中，元素比較與移動的次數是最多的。
2．直接插入排序代碼實現
直接插入排序的代碼如例所示。
6.2.2 直接插入排序
6.2.2 直接插入排序
例的運行結果如下所示。
由程序輸出可以看出，無序序列經過插入排序后，成為遞增的有序序列。
6.2.3 希爾排序
1．希爾排序概述
希爾排序（Shell Sort）是希爾（Donald Shell） 于 1959 年提出的一種排序算法。希爾排序同樣是一種插入排序，它是直接插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序。希爾排序與直接插入排序的不同之處在于，希爾排序會優先比較距離較遠的元素。
希爾排序的核心操作是將序列按照增量（增量等于組的數量）進行分組，然后對每一組中的序列使用直接插入排序算法進行排序。當所有組中的序列都完成排序后，增量變小，按照減小的增量再次分組（分組不影響元素的位置），分組后再進行直接插入排序，以此類推（增量越小，每組的元素就越多）。當增量減小為 1 時，整個序列分為一組，算法結束。
希爾排序在選擇增量時，可以使增量 gap=length/2（length 為序列長度），縮小增量可以使用gap=gap/2 的方式，這種增量可以用一個序列來表示，稱為增量序列。
6.2.3 希爾排序
接下來通過具體的序列對希爾排序算法進行說明。如圖所示，創建一個原始的未排序的序列。
由圖可以計算出，初始增量 gap=length/2=6，則整個序列可以分為 6 組，分別是[18,21]、[9,3]、[7,17]、[5,24]、[13,14]、[16,44]，如圖 所示。
6.2.3 希爾排序
分別對 6 組序列進行直接插入排序（組與組互不影響），如圖所示。
對比圖可知，經過插入排序后，第 2 組的元素 3 與元素 9 交換了位置。完成排序后，減小增量 gap=gap/2=3，則整個序列分為 3 組，如圖所示。
6.2.3 希爾排序
分別對重新分組的 3 組序列進行直接插入排序，如圖所示。
對比圖可知，第 1 組序列經過直接插入排序后為 5–18–21–24，第 2 組序列排序后
為 3–9–13–14，第 3 組序列排序后為 7–16–17–44。再次減小增量 gap=gap/2=1，則將整個序列作為一組，對整個序列進行直接插入排序，如圖所示。
6.2.3 希爾排序
6.2.3 希爾排序
經過最后一次直接插入排序后，序列變為遞增序列。從上述過程中可以看出，每一次改變增量都會進行一次直接插入排序。雖然希爾排序涉及多次插入排序，但就整體而言，希爾排序降低了直接插入排序算法中元素移動與判斷的次數。
2．希爾排序代碼實現
希爾排序算法的代碼參考教材6.2.3節。
例中，每一次確定增量后，選擇分組中的元素與同組中該元素的前一個元素進行對比，如果
滿足交換條件則交換。程序運行結果如下所示。
程序運行結果中，增量序列為 4–2–1，排序后的序列為遞增序列。
6.2.4 直接選擇排序
1．直接選擇排序概述
直接選擇排序（Selection Sort）是比較穩定的排序算法，其時間復雜度在任何情況下都是 O(n 2 )。
直接選擇排序是一種簡單直觀的排序算法，排序過程中，無須占用額外的空間。直接選擇排序的工作原理是：首先在未排序的序列中找到最小（大）元素，存放到已排序序列的末尾；然后從剩余未排序元素中尋找最小（大）元素，放到已排序序列的末尾；以此類推，直到所有元素排序完畢。
由上述描述可知，直接選擇排序就是反復從未排序的序列中取出最小（大）的元素，加入另一個序列，最后得到已經排好的序列。接下來通過具體的序列對直接選擇排序算法進行說明。如圖所示，創建一個原始的未排序的序列。
6.2.4 直接選擇排序
選取第一個元素 5，分別與其他元素進行比較，當比較到元素 4 時，發現元素 4 小于元素 5，然后用元素 4 與其他元素進行對比，對比到元素 3 時，對比結束，將元素 3 放入已排序的序列，如圖所示。
經過第一次排序，元素 3 進入已排序的序列。選取未排序序列中的第一個元素 7 再次進行比較，當比較到元素 4 時，發現元素 4 小于元素 7，然后用元素 4 與其他元素進行比較。元素 4 為最小值，
將其放入已排序的序列，如圖所示。
6.2.4 直接選擇排序
元素 3、4 進入已排序序列。選取元素 7 與其他元素再次進行比較，比較到元素 6 時，開始用元素 6 與其他元素進行比較。元素 5 為最小值，將其放入已排序的序列，如圖所示。
元素 3、4、5 進入已排序序列。選取元素 8 與其他元素再次進行比較，比較到元素 6 時，開始用元素 6 與其他元素進行比較。元素 6 為最小值，將其放入已排序的序列，如圖所示。
6.2.4 直接選擇排序
元素 3、4、5、6 進入已排序序列。選取元素 8 與最后一個元素 7 進行比較。元素 7 為最小值，將其放入已排序的序列，如圖所示。
經過第五次排序后，序列排序結束，為遞增序列。
6.2.4 直接選擇排序
2．直接選擇排序代碼實現
直接選擇排序的代碼參考教材6.2.4節。
例中的直接選擇排序函數每次選擇未排序的第一個元素與其他所有元素進行比較，找到最小元素后，將其與第一個元素進行交換。交換后的第一個元素作為已排序的元素。程序運行結果如下所示。
由運行結果可知，排序后的序列為遞增序列。
6.2.5 堆排序
1．堆排序概述
堆排序（Heap Sort）是利用數據結構堆設計的一種排序算法。堆是一個近似完全二叉樹的結構。如果堆中每個結點的值都大于或等于其左右孩子的值，則該堆稱為大頂堆；如果堆中每個結點的值都小于或等于其左右孩子的值，則該堆稱為小頂堆，如圖所示。
6.2.5 堆排序
如果需要排序后的序列為增序序列，則選擇大頂堆，反之選擇小頂堆。
堆排序算法的具體操作步驟如下所示。
（1）用初始待排序的序列(R 1 ,R 2 ,…R n )構建大頂堆，則此堆為初始的無序區。
（2）將堆頂元素 R 1 與最后一個元素 R n 交換，將得到新的無序區(R 1 ,R 2 …R n-1 )和新的有序區(R n )，同時滿足(R 1 ,R 2 ,…R n-1 )≤(R n )。
（3）由于交換后新的堆頂 R 1 可能違背大頂堆的性質，需要將當前無序區(R 1 ,R 2 ,…R n-1 )調整為新堆，然后將 R 1 與無序區最后一個元素交換，得到新的無序區(R 1 ,R 2 ,…R n-2 )和新的有序區(R n-1 ,R n )。
（4）重復上述過程，直到有序區的元素個數為 n－1，則整個排序過程結束。
6.2.5 堆排序
接下來通過具體的序列對堆排序算法進行說明。如圖所示，構造一個初始未排序的堆。
將堆中的結點按照層序保存到數組中，如圖所示。
6.2.5 堆排序
選取堆的最后一個非葉結點開始調整（lenth/2－1=5/2－1=1），即結點 1，按照從左到右、從下
到上的順序進行調整。判斷結點 1 的左右孩子是否小于該結點，可見結點 4 的值大于結點 1，因此將
結點 4 與結點 1 進行交換，如圖所示。
結點 1 的值變為 8，大于結點 0 的值，因此將結點 1 與結點 0 進行交換，如圖所示。
6.2.5 堆排序
交換結點后，結點 1 的值小于其左右孩子，結點 1、結點 3、結點 4 中結點 4 的值最大，將結點1 與結點 4 進行交換，如圖所示。
經過交換后，無序的堆變為大頂堆。根據該堆與數組的對應關系，得出構造堆的規則。如圖所示，a 為保存結點的數組，i 表示結點在數組的下標以及結點的編號。
6.2.5 堆排序
經過上述交換操作，堆成為大頂堆，其根結點的值大于所有子結點。此時將圖 6.36 中的根結點與末尾結點進行交換（在數組中保存的末尾結點），如圖所示。
經過交換后，結點 4 的值為堆中的最大值，對應數組的末尾，并且該結點將被視為有序序列的第一個元素。
對圖 6.38 中的堆進行調整，使其滿足大頂堆的規則。結點 0 的值小于其左右孩子，因此選擇將結點 2 與結點 0 進行交換（結點 2 的值為當前最大值），如圖所示。
6.2.5 堆排序
結點 0 的值為成為堆中的最大值，此時將堆中的根結點（結點 0）與末尾結點（末尾結點為結點3，結點 4 已排序）進行交換，如圖所示。
經過交換后，結點 3 的值為堆中的最大值，且保存在數組的倒數第二位，結點 3 與結點 4 成為
有序序列。繼續對堆進行調整，將結點 0 與結點 1 進行交換（結點 0 的值小于其左右孩子，且結點 1的值為當前最大值），如圖所示。
6.2.5 堆排序
根結點的值成為堆中的最大值后，選擇將根結點與末尾結點（結點 2）進行交換，如圖所示。
經過交換后，結點 2 的值成為堆積中的最大值，且保存在數組的倒數第三位，成為已排序序列中的元素。
再次對堆進行調整，使其滿足大頂堆的規則，即將結點 0 與結點 1 進行交換，交換后結點 0 的值成為堆中的最大值，如圖所示。
6.2.5 堆排序
按照上述操作規律，接下來將根結點與末尾結點（結點 1）進行交換，交換后頂點 1 的值成為堆中的最大值，并將其保存至數組中，成為已排序序列中的元素，如圖所示。
經過交換，最后一個結點 0 自動加入已排序的序列，至此，堆排序結束，排序后的序列為遞增序列。
通過上述對堆排序的描述可知，其核心操作主要分為三個部分：用無序序列構造一個堆，并調整為一個大頂堆或小頂堆；將堆頂元素與末尾元素進行交換，將最大（小）元素放到數組的末尾；重新調整結構，使堆再次變成大（小）頂堆，再次進行元素交換，將最大（小）放到數組的末尾。反復執行上述過程，每次選出最大（小）元素，從數組的末尾開始依次進行存儲，直到所有元素都被選出，則排序成功。
6.2.5 堆排序
2.堆排序代碼實現
堆排序的代碼參考教材6.2.5節。
堆排序算法的實現比其他排序算法復雜。其中，Make_Heap()函數用來實現第一次堆的調整，第一次調整堆是從堆中最后一個非葉結點開始的。第一次堆調整完成后，堆頂元素一定是整個堆的最大元素，將其與末尾元素進行交換，目的是將最大值存儲到數組的末尾。元素交換導致堆頂元素不再是最大元素，破壞了大頂堆的規則，此刻除了堆頂元素，其他元素仍然滿足大頂堆的規則，因此，后續堆調整都是從堆頂元素開始。Adjust_Heap()函數用來實現某個非葉結點與其子結點的調整，當該非葉結點為根結點時，函數調整的是整個堆。程序運行結果如下所示。
由運行結果可知，通過堆排序算法排序后的序列為遞增序列。
6.2.6 冒泡排序
1．冒泡排序概述
冒泡排序（Bubble Sort）是一種簡單且經典的排序算法。冒泡排序的核心思想是重復遍歷整個序列，從第一個元素開始，兩兩比較相鄰元素的大小，如果反序則交換，直到整個序列變為有序為止。
冒泡排序算法的具體操作步驟如下所示。
（1）比較相鄰元素，從第一個元素開始，即第一個元素與第二個元素比較，如果前一個元素大于后一個元素就進行交換。
（2）每次比較完成后，移動到下一個元素繼續進行比較，直到比較完最后一個元素與倒數第二個元素。
（3）所有元素比較完成后（一輪比較），序列中最大的元素在序列的末尾。
（4）重復上述 3 個步驟。
6.2.6 冒泡排序
接下來通過具體的序列對冒泡排序算法進行說明。如圖所示，創建一個初始未排序的序列。
對該序列進行第一次排序。先比較第一個元素與第二個元素，再比較第二個元素與第三個元素，以此類推。如果前一個元素大于后一個元素，則將二者交換，反之不交換，如圖所示。
6.2.6 冒泡排序
第一次排序后，最大元素 12 位于序列末尾。進行下一輪排序，如圖所示。
第二次排序后，元素 10 位于序列倒數第二位。繼續進行下一輪排序，如圖所示。
6.2.6 冒泡排序
第三次排序后，元素 7 位于序列倒數第三位。繼續進行下一輪排序，如圖所示。
第四次排序后，元素 5 位于序列倒數第四位。繼續進行下一輪排序，如圖所示。
經過排序后，序列為遞增序列。至此，冒泡排序結束。
6.2.6 冒泡排序
2．冒泡排序代碼實現
冒泡排序的代碼如例所示。
6.2.6 冒泡排序
6.2.6 冒泡排序
例中，Bubble_Sort()函數用來實現冒泡排序，其中使用 for 循環嵌套完成排序過程，第一層循環表示排序的輪次，第二層循環用來實現一輪排序（從第一個元素到最后一個元素的比較），每一輪排序都會從未排序的元素中確定一個最大值，并放到未排序序列的末尾。程序運行結果如下所示。
由運行結果可知，通過冒泡排序算法排序后的序列為遞增序列。
6.2.7 快速排序
快速排序（Quick Sort）的核心思想是通過一輪排序將未排序的序列分為獨立的兩部分，使得一部分序列的值比另一部分序列的值小，然后分別對這兩部分序列繼續進行排序，以達到整個序列有序。
快速排序使用分治法將一個序列分為兩個子序列，其具體的算法描述如下。
（1）從序列中選出一個元素，作為基準值。
（2）重新排序，將所有比基準值小的元素放到基準值前，所有比基準值大的元素放到基準值后（與基準值相同的元素可以到任一邊）。
（3）采用遞歸的思想對小于基準值的子序列和大于基準值的子序列排序。
在上述算法描述的基礎上，快速排序可以設計出很多版本。接下來將通過具體的序列展示快速排序的兩個版本，分別為單指針遍歷法與雙指針遍歷法（指針指的是方向選擇，不是語法意義上的指針）。
6.2.7 快速排序
1．單指針遍歷法
如圖所示，創建一個無序的數字序列。
從序列的第一個元素開始，將元素 5 作為基準值，從序列末尾選擇元素與基準值進行比較，即元素 2 與元素 5 進行比較。由于元素 2 小于元素 5，二者進行交換，如圖所示。
6.2.7 快速排序
交換完成后，從序列開頭選擇元素與基準值進行比較，即元素 7 與元素 5 進行比較。由于元素 7大于元素 5，二者進行交換，如圖所示。
從序列末尾選擇元素與基準值進行比較，即元素 3 與元素 5 進行比較。由于元素 3 小于元素 5，二者進行交換，如圖所示。
6.2.7 快速排序
從序列開頭選擇元素與基準值進行比較，即元素 1 與元素 5 進行比較。由于元素 1 小于元素 5，二者無須交換。移動至下一個元素，比較元素 6 與元素 5，元素 6 大于元素 5，二者進行交換，如圖所示。
從序列末尾選擇元素與基準值進行比較，即元素 8 與元素 5 進行比較。由于元素 8 大于元素 5，二者無須交換。移動至下一個元素，比較元素 4 與元素 5，元素 4 小于元素 5，二者進行交換，如圖所示。
6.2.7 快速排序
經過一輪排序后，序列被分為兩個子序列，元素 5 前的所有元素都小于元素 5 后的所有元素。將元素 5（可包含元素 5）前的序列視為一個子序列，元素 5 后的序列視為另一個子序列，接下來繼續采用上述方式，對這兩個子序列進行排序。
先處理第一個子序列，即元素 2 到元素 5，將元素 2 作為基準值。將子序列的末尾元素 5 與元素2 進行比較，元素 5 大于元素 2，無須交換。移動至下一個元素 4，同樣無須交換。再次移動至下一個元素 1，元素 1 小于元素 2，二者進行交換，如圖所示。
6.2.7 快速排序
繼續從子序列的開頭選擇元素與基準值進行比較，即元素 3 與元素 2 進行比較。元素 3 大于元素 2，二者進行交換，如圖所示。
經過交換，子序列再次分為兩個子序列，即元素 1 到元素 2 為一個子序列，元素 3 到元素 5 為另一個子序列。將這兩個序列繼續按照上述方法排序，包括元素 8 到元素 7 的子序列。當所有子序列的元素個數變為 1 時，整個序列的排序工作結束。
由上述操作過程可知，一輪排序會產生兩個子序列，且子序列會繼續產生子序列。排序的輪次越多，子序列越多，子序列中元素的個數越少。無論產生多少子序列，其排序方式不變，因此排序的過程可以采用遞歸的思想來實現。
6.2.7 快速排序
2．單指針遍歷法實現快速排序
采用單指針遍歷法實現快速排序，如例所示。
6.2.7 快速排序
6.2.7 快速排序
例中，Quick_Sort()函數用來實現快速排序，通過函數嵌套實現遞歸操作，遞歸的目的是對每一輪排序產生的子序列進行排序。Quick_Sort()函數中，采用“挖坑填數”的方式實現了元素之間的交換，如圖所示。
6.2.7 快速排序
挖坑填數”通過相互賦值覆蓋掉不需要的數據，實現數據的交換。讀者也可以定義交換元素的函數，使用直接交換的方式完成排序。程序運行結果如下。
由運行結果可知，經過快速排序后的序列為遞增序列。
3．雙指針遍歷法
在單指針遍歷法中，每次都是選擇一個元素與基準值進行比較，而雙指針遍歷法是同時選擇兩個元素與基準值進行比較。如圖所示，創建一個無序序列。
6.2.7 快速排序
圖中，標志 i 處于第一個元素 15 的位置，標志 j 處于末尾元素 12 的位置。將元素 15 作為基準值，將標志 i 向右移動，標志 j 不變。對比標志 i 與標志 j 對應的元素，如圖所示。
將標志 i 對應的元素與標志 j 對應的元素同時與基準值進行對比，元素 17 大于元素 15，元素 12小于元素 15，因此將標志對應的元素進行交換。元素交換后，小于基準值的元素在前，大于基準值的元素在后，標志 i 與 j 分別向右、向左移動一位，如圖所示。
6.2.7 快速排序
由于標志 i 對應的元素 10 小于元素 15，需要將標志 i 繼續向右移動一位，標志 j 位置不變。標志 i 對應的元素 16 大于元素 15，標志 j 對應的元素 13 小于元素 15，因此二者進行交換，如圖所示。
元素交換后，較小的元素排在較大的元素前面。繼續移動標志 i 與標志 j，使標志 i 對應的元素為 14，標志 j 對應的元素為 18，如圖所示。
6.2.7 快速排序
標志 i 對應的元素 14 小于元素 15，標志 j 對應的元素 18 大于元素 15，因此二者不需要交換。繼續移動標志 i 與標志 j（標志 i 與標志 j 都需要移動時，先移動標志 j，如果標志 i 與標志 j 發生重合，將基準值與標志對應的元素進行交換），如圖所示。
元素 14 與基準值交換后，序列分為兩個子序列，即元素 14 到元素 15 為一個序列，元素 18 到元素 17 為一個序列。分別對這兩個子序列采用同樣的方式進行排序，如圖所示。
6.2.7 快速排序
繼續通過移動標志進行排序，直到序列中的元素減少到 1 個為止。雙指針遍歷法與單指針遍歷法一樣，需要采用遞歸的思想實現。
4．雙指針遍歷法實現快速排序
采用雙指針遍歷法實現快速排序，示例代碼參考教材6.2.7節。
例中，partition()函數實現每一輪排序都會產生兩個子序列。Quick_Sort()函數通過嵌套實現遞歸操作，對子序列進行排序。程序運行結果如下所示。
由運行結果可知，排序后的序列為遞增序列。
6.2.8 歸并排序
1．歸并排序概述
歸并排序（Merging Sort）是利用歸并的思想設計的一種排序算法，該算法是采用分治法的一個非常典型的應用。歸并排序是一種穩定的排序方法，性能不受輸入數據的影響。歸并排序的核心思想是將已排序的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列之間有序。
歸并排序算法的具體描述如下。
（1）將長度為 n 的序列分成兩個長度為 n/2 的子序列。
（2）對兩個子序列分別進行歸并排序。
（3）將兩個排序好的子序列合并成一個最終序列。
歸并排序主要的操作是分與合，分指的是將序列分為子序列，合指的是合并子序列。
6.2.8 歸并排序
由于最開始的序列是無序的，因此對該序列采用遞歸的方式進行分割，直到每一個子序列都有序為止，如圖所示。
一個無序的序列經過多次分割，最后每個子序列的元素個數為 1。當子序列的元素個數為 1 時，可以認為該子序列是有序的。
分割完成后，再對子序列采用遞歸的思想進行合并，如圖所示。
6.2.8 歸并排序
圖展示的算法過程中，不僅需要將子序列合并，而且需要對合并的序列進行排序。接下來對圖中的最后一次合并處理進行具體分析，如圖所示。
由于子序列在合并前都是有序的，因此可以從子序列的第一個元素開始進行比較，將較小的元素放入一個新的數組中保存，如圖所示。
6.2.8 歸并排序
圖中，標志 i 與標志 j 分別對應兩個子序列的第一個元素。從第一個元素開始比較，標志 j對應的元素 1 小于標志 i 對應的元素 4，因此將元素 1 存入新數組的第一個位置。移動標志 j 到下一個位置，再次比較標志 i 與標志 j 對應的元素，如圖所示。
標志 j 對應的元素 2 小于標志 i 對應的元素 4，因此將元素 2 存入新數組。移動標志 j 到下一個位置，再次比較標志 i 與標志 j 對應的元素，如圖所示。
6.2.8 歸并排序
標志 j 對應的元素 3 小于標志 i 對應的元素 4，因此將元素 3 存入新數組。移動標志 j 到下一個位置，再次比較標志 i 與標志 j 對應的元素，如圖所示。
標志 j 對應的元素 6 大于標志 i 對應的元素 4，因此將元素 4 存入新數組。移動標志 i 到下一個位置，再次比較標志 i 與標志 j 對應的元素，如圖所示。
6.2.8 歸并排序
標志 j 對應的元素 6 大于標志 i 對應的元素 5，因此將元素 5 存入新數組。移動標志 i 到下一個
位置，再次比較標志 i 與標志 j 對應的元素，如圖 所示。
標志 j 對應的元素 6 小于標志 i 對應的元素 7，因此將元素 6 存入新數組。元素 6 存入數組后，標志 j 無法移動，表示子序列遍歷結束。此時將另一個子序列中剩余的元素按順序依次存入新數組，如圖所示。
6.2.8 歸并排序
至此，已通過比較將所有子序列中的元素加入新數組，形成新的序列。歸并排序中其他合并子序列的操作與上述操作相同。
2．歸并排序代碼實現
歸并排序算法的代碼參考教材6.2.8節。
例中，Merge_Sort()函數通過嵌套實現遞歸排序，Merge()函數用來實現合并子序列。程序運行結果如下所示。
由運行結果可知，排序后的序列為遞增序列。
本章小結
本章主要介紹了算法中的兩種常見操作——查找與排序，包括 4 種常見的查找算法與 7 種排序法。本章從操作原理與代碼實現兩個方面解釋了每一種算法的核心思想。不同的算法在處理不同的情況時，效率也不同。因此，讀者需要在理解這些算法的基礎上，熟練編寫操作代碼，為在實際開發中優化數據操作奠定基礎。

展開更多......

收起↑