# 一、題目描述 證明：在最壞情況下，利用n+ceil(lgn)-2次比較，即可得到n個元素中的第2小元素。（提示：同時找最小元素） # 二、常規方法 使用兩次for循環，分別將數組從前往后掃描。 第一掃次掃描過程中，不斷記錄和更新當前情況下的最小元素。 第二次和掃描過程中，不斷記錄和更新當前情況下的第二小元素。 偽代碼如下： ~~~ Int min = array[0], minId = 0; FOR i in [1, n), i++ DO IF (array[i] < min) DO Min = array[i]; minId = i; DONE DONE Int secId = ( minId = 0 ? 1 : 0 ), sec = array[secId]; FOR i in [secId+1, n), i++ DO IF (i = minId) CONTINUE IF ( array[i] < sec ) DO Sec = array[i]; secId = i; DONE DONE ~~~ # 三、常規方法的比較次數 第一個循環過程中，每次循環內部的比較次數為1次，循環次數即掃描的元素個數為n-1，因此比較第一次循環過程的次數是n-1。 第二個循環過程中，每次循環內部的比較次數也中1次，循環次數即掃描的元素個數為n-2（去去掉了最小元素），因此比較第二次循環過程的次數是n-2。 常規方法的比較次數為(n-1)+(n-2)，即2n-3次。 # 四、方法改進一 在第一次循環求最小元素的過程時，對元素內容一無所知，因此n-1次的比較是必要的，難有優化空間。 在第二次循環求第二小元素的過程時，對元素的內容不再是一無所知。如果充分利用第一次循環所得到的信息，也許可以省掉第二次循環中不必要的比較。 本次優化的重點在第二次循環。 # 五、第一次循環的可用信息 原理： 如果 a > b 且 b > c，那么不需要經過a和c的比較就可以知道 a > c。 信息1： 假設數組中的元素為a, b, c, d, e, f, g … 。 當掃描到元素d時，最小元素為c，可知 a > c, b > c, d > c。 當掃描到元素e時，最小元素變為了e，可知 e > c。 那么 a > c > e, b > c > e, d > c > e， a,b,d不可能是第二小元素或最小元素 c是第二小元素，e是最小元素 信息2： 接著上文繼續掃描，當掃描到元素e時，最小元素為e，結論如上。 當掃描到元素g時，最小元素仍為e，可知f > e, g > e。 那么a > c > e, b > c > e, d > c > e, f > e, g > e a, b, d不可能是第二小元素或最小元素 c, f, g有可能是第二小元素，e是最小元素 # 六、根據第一遍的可用信息作第二次循環 假設已經作過第一次掃描，找到了最小元素，為e，現在要充分利用第一次掃描的信息作第二次掃描。 這一次，我們并不是對除了e以外的所有元素掃描，而是只選擇其中一部分。選擇的依據來自于上一節的內容。 我們大膽猜測，第二小元素的候選值是那些在第一次掃描過程中與e做過直接比較的元素。 證明如下： 1. 在第一次循環的過程中，第二小元素一定與最后元素e直接比較過。 證明： 第一種情況，在數組順序中，第二小元素在e之前出現 在出現之前，第二小元素一直都是被當作當前狀態的最小元素，遇到e之后，因為與e比較失敗，最小元素才變成了e。 第二種情況，在數組順序中，第二小元素在e之后出現 e會與后面的每一個元素直接比較。 2. 沒有與最小元素e直接比較過的元素一定不會是第二小元素 證明過程與1相反，略。 # 七、方法改進一的偽代碼 第一次掃描的比較沒有改變，只是每次比較的過程記錄下來，以便第二次掃描的時候知道某個元素曾經和誰做過比較。 ~~~ Int min = array[0], minId = 0; FOR i in [1, n), i++ DO IF (array[i] < min) DO Min = array[i]; minId = i; QUEUE[i].PUSH(min); ELSE QUEUE[minId].push(array[i]); DONE DONE ~~~ 第二次掃描時，僅取出最小元素所對應的隊列元素做比較 ~~~ Int secId = QUEUE[minId].ELEMET(0) FOR i in [1, QUEUE[minId].size), i++ DO IF (QUEUE[minId].ELEMET(i) < sec ) DO Sec = QUEUE[minId].ELEMET(i); DONE DONE ~~~ # 八、方法改進一的比較次數 第一次掃描的次數仍然為n-1，主要差別在于第二次掃描。 第二次掃描也是FOR循環，每次循環內部的比較次數是1次，總的比較次數取決于 隊列中元素的個數。假設個數為m，那么比較次數為m-1。 為了計算m，我畫了這樣一個圖。葉子結點為數組中的元素。沒有標字母的節點表示其它兩個孩子結點的比較結果。畫出這樣的圖，任假設一個結點為最小元素，都能很清晰地看出其隊列中元素的個數。  我們取兩種最極端的情況： 假如最小元素為A，那么其隊列中的元素為B, C, D，3個元素 假如最小元素為D，那么其隊列中的元素為A, B, C中的最小值，1個元素。 結論，方法改進一的比較次數最多為2n-3，最少為n-1，取決于最小元素所在位置。 # 九、方法改進二 雖然方法改進一相比于常規方法是有了改善，但最多比較次數仍然需要2n-3次，未達到題目所要求。這次我們方找最小元素的過程入手。 上文已經說過，求最元素的過程到少要經過n-1次比較，這一點是難以改變的。但我們仍可以通過調整第一次遍歷方式，使留給第二次遍歷更多有用的信息。盡量讓每個元素與其它元素的比較次數平均化，這樣，當任意一個元素成為最小元素時，它的隊列的元素個數都不會太多。仍然以上文的圖為例：  方法改進一的第一次遍歷可以畫成這一樣的圖，數組中的每一元素是這個二叉樹的葉子結點。假如某一個元素是最小元素，那么它的隊列的元素即該葉子結點的高度。只要將樹平均化，如下圖所示，保證每一個葉子的高度都不會太高，那么每個元素對應的隊列都就不會太大。  # 十、方法改進二的比較次數 方法改進二的偽代碼比較復雜，請大家直接閱讀源代碼。 對于第一次遍歷，比較次數仍為n-1。 對于第二次遍歷，比較次數取決于第一次遍歷轉化生成的二叉樹的高度h。 將二叉樹平均化以后，樹的高度為h= ceil[lgn]。 結論，方法改進二的比較次數最多為n+ ceil[lgn]-2。 # 十一、代碼 產品代碼 [https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter9/Exercise9_1_1.cpp](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter9/Exercise9_1_1.cpp) 測試代碼 [https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter9/Exercise9_1_1Test.cpp](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter9/Exercise9_1_1Test.cpp)