第五章：排序演算法¹

Part1：內部排序²

1、三大經典排序演算法

1.1 插入排序

將待排序記錄插入到已排好序的序列中

1. 直接插入排序

   每次將一個記錄使用順序查找³，插入到前面已經排好序的子序列中

2. 折半插入排序

   在1的基礎之上，對子序列進行折半查找

3. 希爾排序（Shell Sort）

   先追求表中元素部分有序，然后逐漸逼近全域有序，每次有n個記錄使用直接插入排序（n=length/distance）

   具體操作：選擇一個距離d，另表中相距d的元素之間使用直接插入排序，另d=d/2，重復該程序

1.2選擇排序

每次均從無序序列中找到一個最值，并且放入有序序列中，并將其從無序序列中洗掉

1. 簡單選擇排序

   遍歷無序序列，從中找到最值并且固定，從剩下的無需序列中重復該程序

2. 堆排序⁴

   • 堆：即用順序結構存盤的完全二叉樹

     • 大根堆：根結點>左右孩子（就算是數值上相同，也認為是嚴格大于）
     • 小根堆：根結點<左右孩子

   • 具體操作（以大根堆為例）

     將無序序列視為堆，并將其成為大根堆，從而選出最大值，并且加入有序序列，對剩下的序列重復該操作即可

1.3交換排序

根據比較結果，交換兩個元素在序列中的位置，故稱為交換

1. 冒泡排序

   比較兩個相鄰元素的值，如果不符合序，則交換他們，

   在這個程序中，各個元素會逐漸到達他們最終的位置，就像水底的氣泡向上冒一樣，故稱之為冒泡排序，（每次均可確定一個最值）

2. 快速排序⁵

   基本思路：挖坑填樹+分治法

   即選擇一個基數，對陣列磁區（左邊均小于這個基數，右邊均大于這個基數），對左右區間重復該程序直到左右區間只有1或者0個數，

2、特殊排序演算法

2.1 歸并排序（Merge Sort）

將n個有序的序列合并為1個成為n路歸并，而歸并排序，是將原來含有n個元素的無序序列視為n個有序的序列，然后歸并

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-B7nK3qf7-1641112616224)(./image/chapter05/6.jpeg)]

2.2 基數排序（Radix Sort）

基本思想：通過比較元素各位大小，然后排序

實作思路：采用一個輔助佇列，先比低位，按序入隊并出隊，然后再比較高位，重復

Part2：外部排序

由于資料元素太多無法一次性調入記憶體，故只能每次一部分一部分的調入記憶體排序，稱為外部排序，

1、實作思路

在記憶體中開辟n個緩沖區（n >= 2+1）⁶將資料元素磁區讀入，然后

• 緩沖區內部使用內部排序使其有序
• 緩沖區之間使用歸并排序，使其生成初始歸并段并寫回外存
• 從外存中讀取不同的歸并段，并使用歸并排序，寫回外存，重復至歸并段只有一個

2、對該程序的分析

每次排序，都需要讀寫in緩沖區（1中的例子）個數的磁盤塊（Block）由于磁盤塊讀寫時間遠大于內部排序和歸并排序的時間，所有影響該程序的時間因素主要是磁盤讀寫時間，

設Block個數為x，采用k路歸并（in緩沖區個數有k個），歸并次數為m次，r為初始歸并段個數
磁 盤 讀 寫 次 數 = 2 ? x + m ? 2 ? x 磁盤讀寫次數=2*x+m*2*x 磁盤讀寫次數=2?x+m?2?x
其中

• 第一個2x表示生成初始歸并段所需要讀寫的次數（讀入為x次，寫入為x次）

• 第二個部分m2x表示歸并排序所需讀寫次數

而
m = ? l o g k r ? r = ? l o g k x ? m=\lceil log_k r\rceil \\ r=\lceil log_k x\rceil m=?logk?r?r=?logk?x?
由于x無法改變，所以我們只能考慮減小m來減少磁盤讀寫時間

• 增大k——多路平衡歸并——敗者樹優化
• 減小r——增加歸并段的長度——置換-選擇排序

3、敗者樹

采用多路平衡歸并需要付出兩個代價，一個是需要多片緩沖區，一個是需要k-1次的關鍵詞對比，為了優化多路平衡歸并，只能從k-1次的關鍵詞對比下手了，

在k-1次對比中，如果不是第一次對比，那么可以根據以往的比較記錄快速比較出最值，即敗者樹，

通常以一顆完全二叉樹來表示這種資料結構，其葉子節點表示元素，非葉子節點表示失敗者；

4、置換-選擇排序

設外部排序有m個記錄，而in緩沖區中可存放n個記錄，則初始歸并段數量為(m>>n)
? m / n ? \lceil m/n \rceil ?m/n?
可以使用置換-選擇排序來增大歸并段長度，從而減少歸并段數量

基本思想：采用一個temp來記錄當前段的最大值，并且不斷輸出可用最小值，知道無可用最小值為止，這樣為一段，重復該程序

通過置換-選擇排序生成的歸并段長度是不同的，這樣子就造成了一個問題，把這些長度不同的歸并段寫回外存的開銷是不同的，顯然長度越長，開銷越大，這就相當于給這些歸并段賦予了權重，我們可以采用哈夫曼樹的思想來優化，即為最佳歸并樹

5、最佳歸并樹

例如當我們有5個歸并段，采用二路歸并時

同理可以擴展至k路歸并

對于k叉歸并（k>2），有時歸并段的數量不滿足嚴格k叉樹，這個時候我們就要補充幾個長度為0的虛段使其滿足，（技巧，如果題目中只告訴你目前有幾個歸并段，和k的值，那么將歸并段權重假設為一樣即可，這樣子一下就可看出需要補充幾個虛段）

Part end：參考文獻和一些說明：