選擇排序的演變

來自專欄山間詞話

一、問題衍生

假設有一串葡萄，小朋友開始吃這一串葡萄，那麼怎麼開始吃呢？

假設這個小朋友制定的策略是從大的開始吃，那麼他不斷的從這串葡萄裡面「挑選出」最大的，然後不斷吃，一直到這串葡萄吃完為止。

這裡我們人類可以知道怎麼選擇最大的，但是對於機器而言，這是一個黑箱操作。我們需要實現這個「挑選」的步驟。

首先需要給每個葡萄進行編號。

二、Basic selection sorting

array：xs

1）、演算法思想（以降序排列為例）：

1. 如果xs是空集，則結束，否則2；
2. 將剩餘的集合中從開始的index不斷向後比較，將較大的拿出來放到隊列的後面，並從集合中刪除這個元素；
3. 一直操作2直到xs為空。

我們可以知道該演算法會在刪除元素這個操作中消耗過多時間。需要額外 的時間，我們可以想到，只需要找到那個最大的元素，並與index的元素進行交換就行了，這是一個 的時間。

2)、改進後的演算法（降序）：

1. 如果xs是空集，則結束，否則2；
2. 將剩餘的集合中從開始的index不斷向後比較，將較大和index位置的元素進行交換；
3. 一直操作2直到xs為空。

3)、代碼：

def find_min(xs,i): n = len(xs) minIndex = i for index in range(i+1,n): if xs[index]< xs[minIndex]: minIndex = index return minIndexdef ssort1(xs): n = len(xs) for index in range(n-1): minIndex = find_min(xs,index) if minIndex != index: (xs[index],xs[minIndex]) = (xs[minIndex],xs[index])

Note: 這裡有兩個地方：

0、當待排序的數組只有一個元素的時候，不需要再次比較了；

1、每次從index處開始，只需要從index+1處開始比較就好了；

2、開始交換數據的時候，如果發現index的值和minIndex一樣，則不需要交換，因為本來就是需要的那個數據了。

三、Cock-tail sort

從上面的演算法中我們可以知道：

如果我們採用選擇最大元素的comparator，我們可以得到降序（descending）的元素，但是假設我們從後開始遍歷，將選擇到的每次最大者和尾元素進行交換，那麼，我們將得到升序（ascending）的元素。

這告訴我們，因為每次遍歷中，我們可以同時得到最大者和最小者，這樣，從頭部和尾部一起開始的遍歷，將使得排序演算法的時間減半。

def cock_search(xs,startIndex,endIndex): minIndex = startIndex maxIndex = endIndex-1 for i in range(startIndex+1,endIndex): if xs[i]<xs[minIndex]: minIndex = i if xs[maxIndex]<xs[i]: maxIndex = i return minIndex,maxIndexdef sort_cock_tail(xs): n = len(xs) for index in range(n//2): minIndex,maxIndex = cock_search(xs,index,n-index) (xs[index],xs[minIndex]) = (xs[minIndex],xs[index]) (xs[n-1-index],xs[maxIndex]) = (xs[maxIndex],xs[n-1-index])

很明顯，這樣我們只需要遍歷一半元素就好了。

四、Major improvement

注意到上面的演算法的時間複雜度為 , 很明顯我們需要外層的遍歷，我們我們需要想辦法怎樣才能在每次檢索最大值（最小值）的時候能夠擁有較小的時間複雜度。

想到世界盃的賽制，拿到冠軍的一定是最強的，但是第二的卻值得商榷。

如上圖所示，16一定是最大者，但是元素15在第一輪即被淘汰。我們目標就是如何尋找15這個元素。

1) 演算法描述（以最大堆為例）：

1. 從數據中構建一個Tournament Tree，這樣root就是最大者；
2. 從root開始自頂向下開始遍歷，並將所有的root值都置為-INF;
3. 從最下面的-INF開始自下向上開始遍歷，這樣，第二大的就成為root了；
4. 如此往複，直到所有元素已經遍歷遍了。

演算法實現參照：

Donald E. Knuth. ``The Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition). Addison-Wesley Professional; 2 edition (May 4, 1998) ISBN-10: 0201896850 ISBN-13: 978-0201896855

2）時間複雜度

該演算法的時間消耗在：

1、構建Tournament Tree；（一次構建完成）

2、選擇最大的值。（該操作持續n次）

每次選擇最大值的時間複雜度是 ,故而所有的時間複雜度是 。注意到構建Tournament Tree的時間為 ，但是只有一次。

五、一些提升空間

從上面的介紹中，我們得到最後的selecting sort的時間邊界為 ,但是當我們考慮到空間利用的時候，我們發現，我們構建Tournament Tree需要2n的空間（leaves為n，branches為n），並且在尋找並pop最大值時，很多節點是-INF，這部分空間消耗是否可以減少或者去除？

我們想到：binary heap擁有這樣的性質：

1. 用array去存儲數據結構，這樣，我們不在需要額外的2n空間；
2. 頂部即為最大（最小）值；
3. 提供了較為方便的pop的操作。

故而，使用heap能較好的幫助我們。

此處不表，下回再見！