面試中，有下面的問答：
問：有很多個無序的數，我們姑且假定它們各不相等，怎麼選出其中最大的若幹個數呢？
答：可以這樣寫：int array[100] ……
問：好，如果有更多的元素呢？
答：那可以改為：int array[1000] ……
問：如果我們有很多元素，例如1億個浮點數，怎麼辦？
答：個，十，百，千，萬……那可以寫：float array [100 000 000] ……
問：這樣的程式能編譯運作麼？
答：嗯……我從來沒寫過這麼多的0 ……
【解法一】
當學生們信筆寫下float array [10000000]，他們往往沒有想到這個資料結構要如何在電腦上實作，是從目前程式的棧（Stack）中配置設定，還是堆（Heap），還是電腦的記憶體也許放不下這麼大的東西？
我們先假設元素的數量不大，例如在幾千個左右，在這種情況下，那我們就排序一下吧。在這裡，快速排序或堆排序都是不錯的選擇，他們的平均時間複雜度都是O（N * log2N）。然後取出前K個，O（K）。總時間複雜度O（N * log2N）+ O（K） = O（N * log2N）。
你一定注意到了，當K=1時，上面的算法也是O（N * log2N）的複雜度，而顯然我們可以通過N-1次的比較和交換得到結果。上面的算法把整個數組都進行了排序，而原題目隻要求最大的K個數，并不需要前K個數有序，也不需要後N-K個數有序。
怎麼能夠避免做後N-K個數的排序呢？我們需要部分排序的算法，選擇排序和交換排序都是不錯的選擇。把N個數中的前K大個數排序出來，複雜度是O（N * K）。
那一個更好呢？O（N * log2N）還是O（N * K）？這取決于K的大小，這是你需要在面試者那裡弄清楚的問題。在K（K < = log2N）較小的情況下，可以選擇部分排序。
在下一個解法中，我們會通過避免對前K個數排序來得到更好的性能。
【解法二】
回憶一下快速排序，快排中的每一步，都是将待排資料分做兩組，其中一組的資料的任何一個數都比另一組中的任何一個大，然後再對兩組分别做類似的操作，然後繼續下去……
在本問題中，假設N個數存儲在數組S中，我們從數組S中随機找出一個元素X，把數組分為兩部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。
這時，有兩種可能性：
1. Sa中元素的個數小于K，Sa中所有的數和Sb中最大的K-|Sa|個元素（|Sa|指Sa中元素的個數）就是數組S中最大的K個數。
2. Sa中元素的個數大于或等于K，則需要傳回Sa中最大的K個元素。
這樣遞歸下去，不斷把問題分解成更小的問題，平均時間複雜度O（N * log2K）。僞代碼如下：
代碼清單2-11
***Kbig(S, k):
if(k <= 0):
return [] // 傳回空數組
if(length S <= k):
return S
(Sa, Sb) = Partition(S)
return Kbig(Sa, k).Append(Kbig(Sb, k – length Sa)
***Partition(S):
Sa = [] // 初始化為空數組
Sb = [] // 初始化為空數組
// 随機選擇一個數作為分組标準，以避免特殊資料下的算法退化
// 也可以通過對整個資料進行洗牌預處理實作這個目的
// Swap(S[1], S[Random() % length S])
p = S[1]
for i in [2: length S]:
S[i] > p ? Sa.Append(S[i]) : Sb.Append(S[i])
// 将p加入較小的組，可以避免分組失敗，也使分組更均勻，提高效率
length Sa < length Sb ? Sa.Append(p) : Sb.Append(p)
return (Sa, Sb)
【解法三】
尋找N個數中最大的K個數，本質上就是尋找最大的K個數中最小的那個，也就是第K大的數。可以使用二分搜尋的政策來尋找N個數中的第K大的數。對于一個給定的數p，可以在O（N）的時間複雜度内找出所有不小于p的數。假如N個數中最大的數為Vmax，最小的數為Vmin，那麼這N個數中的第K大數一定在區間[Vmin, Vmax]之間。那麼，可以在這個區間内二分搜尋N個數中的第K大數p。僞代碼如下：
代碼清單2-12
while(Vmax – Vmin > delta)
{
Vmid = Vmin + (Vmax - Vmin) * 0.5;
if(f(arr, N, Vmid) >= K)
Vmin = Vmid;
else
Vmax = Vmid;
}
僞代碼中f（arr, N, Vmid）傳回數組arr[0, …, N-1]中大于等于Vmid的數的個數。
上述僞代碼中，delta的取值要比所有N個數中的任意兩個不相等的元素內插補點之最小值小。如果所有元素都是整數，delta可以取值0.5。循環運作之後，得到一個區間（Vmin, Vmax），這個區間僅包含一個元素（或者多個相等的元素）。這個元素就是第K大的元素。整個算法的時間複雜度為O（N * log2（|Vmax - Vmin| /delta））。由于delta的取值要比所有N個數中的任意兩個不相等的元素內插補點之最小值小，是以時間複雜度跟資料分布相關。在資料分布平均的情況下，時間複雜度為O（N * log2（N））。
在整數的情況下，可以從另一個角度來看這個算法。假設所有整數的大小都在[0, 2m-1]之間，也就是說所有整數在二進制中都可以用m bit來表示（從低位到高位,分别用0, 1, …, m-1标記）。我們可以先考察在二進制位的第（m-1）位，将N個整數按該位為1或者0分成兩個部分。也就是将整數分成取值為[0, 2m-1-1]和[2m-1, 2m-1]兩個區間。前一個區間中的整數第（m-1）位為0，後一個區間中的整數第（m-1）位為1。如果該位為1的整數個數A大于等于K，那麼，在所有該位為1的整數中繼續尋找最大的K個。否則，在該位為0的整數中尋找最大的K-A個。接着考慮二進制位第（m-2）位，以此類推。思路跟上面的浮點數的情況本質上一樣。
對于上面兩個方法，我們都需要周遊一遍整個集合，統計在該集合中大于等于某一個數的整數有多少個。不需要做随機通路操作，如果全部資料不能載入記憶體，可以每次都周遊一遍檔案。經過統計，更新解所在的區間之後，再周遊一次檔案，把在新的區間中的元素存入新的檔案。下一次操作的時候，不再需要周遊全部的元素。每次需要兩次檔案周遊，最壞情況下，總共需要周遊檔案的次數為2 * log2（|Vmax - Vmin|/delta）。由于每次更新解所在區間之後，元素數目會減少。當所有元素能夠全部載入記憶體之後，就可以不再通過讀寫檔案的方式來操作了。
此外，尋找N個數中的第K大數，是一個經典問題。理論上，這個問題存線上性算法。不過這個線性算法的常數項比較大，在實際應用中效果有時并不好。
【解法四】
我們已經得到了三個解法，不過這三個解法有個共同的地方，就是需要對資料通路多次，那麼就有下一個問題，如果N很大呢，100億？（更多的情況下，是面試者問你這個問題）。這個時候資料不能全部裝入記憶體（不過也很難說，說知道以後會不會1T記憶體比1斤白菜還便宜），是以要求盡可能少的周遊所有資料。
不妨設N > K，前K個數中的最大K個數是一個退化的情況，所有K個數就是最大的K個數。如果考慮第K+1個數X呢？如果X比最大的K個數中的最小的數Y小，那麼最大的K個數還是保持不變。如果X比Y大，那麼最大的K個數應該去掉Y，而包含X。如果用一個數組來存儲最大的K個數，每新加入一個數X，就掃描一遍數組，得到數組中最小的數Y。用X替代Y，或者保持原數組不變。這樣的方法，所耗費的時間為O（N * K）。
進一步，可以用容量為K的最小堆來存儲最大的K個數。最小堆的堆頂元素就是最大K個數中最小的一個。每次新考慮一個數X，如果X比堆頂的元素Y小，則不需要改變原來的堆，因為這個元素比最大的K個數小。如果X比堆頂元素大，那麼用X替換堆頂的元素Y。在X替換堆頂元素Y之後，X可能破壞最小堆的結構（每個結點都比它的父親結點大），需要更新堆來維持堆的性質。更新過程花費的時間複雜度為O（log2K）。
圖2-1
圖2-1是一個堆，用一個數組h[]表示。每個元素h[i]，它的父親結點是h[i/2]，兒子結點是h[2 * i + 1]和h[2 * i + 2]。每新考慮一個數X，需要進行的更新操作僞代碼如下:
代碼清單2-13
if(X > h[0])
{
h[0] = X;
p = 0;
while(p < K)
{
q = 2 * p + 1;
if(q >= K)
break;
if((q < K – 1) && (h[q + 1] < h[q]))
q = q + 1;
if(h[q] < h[p])
{
t = h[p];
h[p] = h[q];
h[q] = t;
p = q;
}
else
break;
}
}
是以，算法隻需要掃描所有的資料一次，時間複雜度為O（N * log2K）。這實際上是部分執行了堆排序的算法。在空間方面，由于這個算法隻掃描所有的資料一次，是以我們隻需要存儲一個容量為K的堆。大多數情況下，堆可以全部載入記憶體。如果K仍然很大，我們可以嘗試先找最大的K’個元素，然後找第K’+1個到第2 * K’個元素，如此類推（其中容量K’的堆可以完全載入記憶體）。不過這樣，我們需要掃描所有資料ceil[1]（K/K’）次。
【解法五】
上面類快速排序的方法平均時間複雜度是線性的。能否有确定的線性算法呢？是否可以通過改進計數排序、基數排序等來得到一個更高效的算法呢？答案是肯定的。但算法的适用範圍會受到一定的限制。
如果所有N個數都是正整數，且它們的取值範圍不太大，可以考慮申請空間，記錄每個整數出現的次數，然後再從大到小取最大的K個。比如，所有整數都在（0, MAXN）區間中的話，利用一個數組count[MAXN]來記錄每個整數出現的個數（count[i]表示整數i在所有整數中出現的個數）。我們隻需要掃描一遍就可以得到count數組。然後，尋找第K大的元素：
代碼清單2-14
for(sumCount = 0, v = MAXN – 1; v >= 0; v--)
{
sumCount += count[v];
if(sumCount >= K)
break;
}
return v;
極端情況下，如果N個整數各不相同，我們甚至隻需要一個bit來存儲這個整數是否存在。
當實際情況下，并不一定能保證所有元素都是正整數，且取值範圍不太大。上面的方法仍然可以推廣适用。如果N個數中最大的數為Vmax，最小的數為Vmin，我們可以把這個區間[Vmin, Vmax]分成M塊，每個小區間的跨度為d =（Vmax – Vmin）/M，即 [Vmin, Vmin+d], [Vmin + d, Vmin + 2d],……然後，掃描一遍所有元素，統計各個小區間中的元素個數，跟上面方法類似地，我們可以知道第K大的元素在哪一個小區間。然後，再對那個小區間，繼續進行分塊處理。這個方法介于解法三和類計數排序方法之間，不能保證線性。跟解法三類似地，時間複雜度為O（（N+M）* log2M（|Vmax - Vmin|/delta））。周遊檔案的次數為2 * log2M（|Vmax - Vmin|/delta）。當然，我們需要找一個盡量大的M，但M取值要受記憶體限制。
在這道題中，我們根據K和N的相對大小，設計了不同的算法。在實際面試中，如果一個面試者能針對一個問題，說出多種不同的方法，并且分析它們各自适用的情況，那一定會給人留下深刻印象。
注：本題目的解答中用到了多種排序算法，這些算法在大部分的算法書籍中都有講解。掌握排序算法對工作也會很有幫助。
擴充問題
1. 如果需要找出N個數中最大的K個不同的浮點數呢？比如，含有10個浮點數的數組（1.5, 1.5, 2.5, 2.5, 3.5, 3.5, 5, 0, -1.5, 3.5）中最大的3個不同的浮點數是（5, 3.5, 2.5）。
2. 如果是找第k到m（0 < k < = m < = n）大的數呢？
3. 在搜尋引擎中，網絡上的每個網頁都有“權威性”權重，如page rank。如果我們需要尋找權重最大的K個網頁，而網頁的權重會不斷地更新，那麼算法要如何變動以達到快速更新（incremental update）并及時傳回權重最大的K個網頁？
提示：堆排序？當每一個網頁權重更新的時候，更新堆。還有更好的方法嗎？
4. 在實際應用中，還有一個“精确度”的問題。我們可能并不需要傳回嚴格意義上的最大的K個元素，在邊界位置允許出現一些誤差。當使用者輸入一個query的時候，對于每一個文檔d 來說，它跟這個query之間都有一個相關性衡量權重f （query, d）。搜尋引擎需要傳回給使用者的就是相關性權重最大的K個網頁。如果每頁10個網頁，使用者不會關心第1000頁開外搜尋結果的“精确度”，稍有誤差是可以接受的。比如我們可以傳回相關性第10 001大的網頁，而不是第9999大的。在這種情況下，算法該如何改進才能更快更有效率呢？網頁的數目可能大到一台機器無法容納得下，這時怎麼辦呢？
提示：歸并排序？如果每台機器都傳回最相關的K個文檔，那麼所有機器上最相關K個文檔的并集肯定包含全集中最相關的K個文檔。由于邊界情況并不需要非常精确，如果每台機器傳回最好的K’個文檔，那麼K’應該如何取值，以達到我們傳回最相關的90%*K個文檔是完全精确的，或者最終傳回的最相關的K個文檔精确度超過90%（最相關的K個文檔中90%以上在全集中相關性的确排在前K），或者最終傳回的最相關的K個文檔最差的相關性排序沒有超出110%*K。
5. 如第4點所說，對于每個文檔d，相對于不同的關鍵字q1, q2, …, qm，分别有相關性權重f（d, q1），f（d, q2）, …, f（d, qm）。如果使用者輸入關鍵字qi之後，我們已經獲得了最相關的K個文檔，而已知關鍵字qj跟關鍵字qi相似，文檔跟這兩個關鍵字的權重大小比較靠近，那麼關鍵字qi的最相關的K個文檔，對尋找qj最相關的K個文檔有沒有幫助呢？
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)