每日一道算法題7—— 查找最大（小）的k個元素

http://blog.csdn.net/v_july_v/article/details/6370650

http://blog.csdn.net/insistgogo/article/details/7689297

下面，我試圖用最清晰易懂，最易令人了解的思維或方式闡述有關尋找最小的k個數這個問題（這幾天一直在想，除了計數排序外，這題到底還有沒有其它的O（n）的算法? ）。希望，有任何問題，歡迎不吝指正。謝謝。

尋找最小的k個數

題目描述：5.查找最小的k個元素

題目：輸入n個整數，輸出其中最小的k個。

例如輸入1，2，3，4，5，6，7和8這8個數字，則最小的4個數字為1，2，3和4。

第一節、各種思路，各種選擇

0、 咱們先簡單的了解，要求一個序列中最小的k個數，按照慣有的思維方式，很簡單，先對這個序列從小到大排序，然後輸出前面的最小的k個數即可。

1、 至于選取什麼的排序方法，我想你可能會第一時間想到快速排序，我們知道，快速排序平均所費時間為n*logn，然後再周遊序列中前k個元素輸出，即可，總的時間複雜度為O（n*logn+k）=O（n*logn）。

2、 咱們再進一步想想，題目并沒有要求要查找的k個數，甚至後n-k個數是有序的，既然如此，咱們又何必對所有的n個數都進行排序列?
這時，咱們想到了用選擇或交換排序，即周遊n個數，先把最先周遊到得k個數存入大小為k的數組之中，對這k個數，利用選擇或交換排序，找到k個數中的最大數kmax（kmax設為k個元素的數組中最大元素），用時O（k）（你應該知道，插入或選擇排序查找操作需要O（k）的時間），後再繼續周遊後n-k個數，x與kmax比較：如果x<kmax，則x代替kmax，并再次重新找出k個元素的數組中最大元素kmax‘（多謝kk791159796 提醒修正）；如果x>kmax，則不更新數組。這樣，每次更新或不更新數組的所用的時間為O（k）或O（0），整趟下來，總的時間複雜度平均下來為：n*O（k）=O（n*k）。

3、 當然，更好的辦法是維護k個元素的最大堆，原理與上述第2個方案一緻，即用容量為k的最大堆存儲最先周遊到的k個數，并假設它們即是最小的k個數，建堆費時O（k）後，有k1<k2<...<kmax（kmax設為大頂堆中最大元素）。繼續周遊數列，每次周遊一個元素x，與堆頂元素比較，x<kmax，更新堆（用時logk），否則不更新堆。這樣下來，總費時O（k+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各項操作時間複雜度均為logk（不然，就如上述思路2所述：直接用數組也可以找出前k個小的元素，用時O（n*k））。

4、 按程式設計之美第141頁上解法二的所述，類似快速排序的劃分方法，N個數存儲在數組S中，再從數組中随機選取一個數X（随機選取樞紐元，可做到線性期望時間O（N）的複雜度，在第二節論述），把數組劃分為Sa和Sb倆部分，Sa<=X<=Sb，如果要查找的k個元素小于Sa的元素個數，則傳回Sa中較小的k個元素，否則傳回Sa中k個小的元素+Sb中小的k-|Sa|個元素。像上述過程一樣，這個運用類似快速排序的partition的快速選擇SELECT算法尋找最小的k個元素，在最壞情況下亦能做到O（N）的複雜度。不過值得一提的是，這個快速選擇SELECT算法是選取數組中“中位數的中位數”作為樞紐元，而非随機選取樞紐元。

5、 RANDOMIZED-SELECT，每次都是随機選取數列中的一個元素作為主元，在0（n）的時間内找到第k小的元素，然後周遊輸出前面的k個小的元素。 如果能的話，那麼總的時間複雜度為線性期望時間：O（n+k）=O（n）（當k比較小時）。
           

Ok，稍後第二節中，我會具體給出RANDOMIZED-SELECT(A, p, r, i)的整體完整僞碼。在此之前，要明确一個問題：我們通常所熟知的快速排序是以固定的第一個或最後一個元素作為主元，每次遞歸劃分都是不均等的，最後的平均時間複雜度為：O（n*logn）,但RANDOMIZED-SELECT與普通的快速排序不同的是，每次遞歸都是随機選擇序列從第一個到最後一個元素中任一一個作為主元。

6、 線性時間的排序，即計數排序，時間複雜度雖能達到O（n），但限制條件太多，不常用。

7、updated： huaye502在本文的評論下指出：“可以用最小堆初始化數組，然後取這個優先隊列前k個值。複雜度O(n)+k*O(log n)”。huaye502的意思是針對整個數組序列建最小堆，建堆所用時間為O（n）（算法導論一書上第6章第6.3節已經論證，線上性時間内，能将一個無序的數組建成一個最小堆），然後取堆中的前k個數，總的時間複雜度即為：O（n+k*logn）。

關于上述第7點思路的繼續闡述：至于思路7的O（n+k*logn）是否小于上述思路3的O（n*logk），即O（n+k*logn）?< O（n*logk）。粗略數學證明可參看如下第一幅圖，我們可以這麼解決：當k是常數，n趨向于無窮大時，求（n*logk）/（n+k*logn）的極限T，如果T>1，那麼可得O（n*logk）>O（n+k*logn），也就是O（n+k*logn）< O（n*logk）。雖然這有違我們慣常的思維，然事實最終證明的确如此，這個極值T=logk>1，即采取建立n個元素的最小堆後取其前k個數的方法的複雜度小于采取正常的建立k個元素最大堆後通過比較尋找最小的k個數的方法的複雜度。但，最重要的是，如果建立n個元素的最小堆的話，那麼其空間複雜度勢必為O（N），而建立k個元素的最大堆的空間複雜度為O（k）。是以，綜合考慮，我們一般還是選擇用建立k個元素的最大堆的方法解決此類尋找最小的k個數的問題。

也可以如gbb21所述粗略證明：要證原式k+n*logk-n-k*logn>0，等價于證（logk-1）n-k*logn+k>0。當when n -> +/inf（n趨向于正無窮大）時，logk-1-0-0>0，即隻要滿足logk-1>0即可。原式得證。即O（k+n*logk）>O（n+k*logn） =>O（n+k*logn）< O（n*logk），與上面得到的結論一緻。

事實上，是建立最大堆還是建立最小堆，其實際的程式運作時間相差并不大，運作時間都在一個數量級上。因為後續，我們還專門寫了個程式進行測試，即針對1000w的資料尋找其中最小的k個數的問題，采取兩種實作，一是采取正常的建立k個元素最大堆後通過比較尋找最小的k個數的方案，一是采取建立n個元素的最小堆，然後取其前k個數的方法，發現兩相比較，運作時間實際上相差無幾。結果可看下面的第二幅圖。

8、@lingyun310：與上述思路7類似，不同的是在對元素數組原地建最小堆O(n)後，然後提取K次，但是每次提取時，換到頂部的元素隻需要下移頂多k次就足夠了，下移次數逐次減少（而上述思路7每次提取都需要logn，是以提取k次，思路7需要k*logn。而本思路8隻需要K^2）。此種方法的複雜度為O(n+k^2)。@July：對于這個O（n+k^2）的複雜度，我相當懷疑。因為據我所知，n個元素的堆，堆中任何一項操作的複雜度皆為logn，是以按理說，lingyun310方法的複雜度應該跟下述思路8一樣，也為O（n+k*logn），而非O（n+k*k）。ok，先放到這，待時間考證。06.02。
           

updated：

經過和幾個朋友的讨論，已經證明，上述思路7lingyun310所述的思路應該是完全可以的。下面，我來具體解釋下他的這種方法。

我們知道，n個元素的最小堆中，可以先取出堆頂元素得到我們第1小的元素，然後把堆中最後一個元素（較大的元素）上移至堆頂，成為新的堆頂元素（取出堆頂元素之後，把堆中下面的最後一個元素送到堆頂的過程可以參考下面的第一幅圖。至于為什麼是怎麼做，為什麼是把最後一個元素送到堆頂成為堆頂元素，而不是把原來堆頂元素的兒子送到堆頂呢?具體原因可參考相關書籍）。

此時，堆的性質已經被破壞了，是以此後要調整堆。怎麼調整呢?就是一般人所說的針對新的堆頂元素shiftdown，逐漸下移（因為新的堆頂元素由最後一個元素而來，比較大嘛，既然是最小堆，當然大的元素就要下沉到堆的下部了）。下沉多少步呢?即如lingyun310所說的，下沉k次就足夠了。

下移k次之後，此時的堆頂元素已經是我們要找的第2小的元素。然後，取出這個第2小的元素（堆頂元素），再次把堆中的最後一個元素送到堆頂，又經過k-1次下移之後（此後下移次數逐漸減少，k-2，k-3,…k=0後算法中斷）….，如此重複k-1趟操作，不斷取出的堆頂元素即是我們要找的最小的k個數。雖然上述算法中斷後整個堆已經不是最小堆了，但是求得的k個最小元素已經滿足我們題目所要求的了，就是說已經找到了最小的k個數，那麼其它的咱們不管了。

我可以再舉一個形象易懂的例子。你可以想象在一個水桶中，有很多的氣泡，這些氣泡從上到下，總體的趨勢是逐漸增大的，但卻不是嚴格的逐次大（正好這也符合最小堆的性質）。ok，現在我們取出第一個氣泡，那這個氣泡一定是水桶中所有氣泡中最小的，把它取出來，然後把最下面的那個大氣泡（但不一定是最大的氣泡）移到最上面去，此時違反了氣泡從上到下總體上逐漸變大的趨勢，是以，要把這個大氣泡往下沉，下沉到哪個位置呢?就是下沉k次。下沉k次後，最上面的氣泡已經肯定是最小的氣泡了，把他再次取出。然後又将最下面最後的那個氣泡移至最上面，移到最上面後，再次讓它逐次下沉，下沉k-1次…，如此循環往複，最終取到最小的k個氣泡。

ok，是以，上面方法所述的過程，更進一步來說，其實是第一趟調整保持第0層到第k層是最小堆，第二趟調整保持第0層到第k-1層是最小堆…，依次類推。但這個思路隻是下述思路8中正規的最小堆算法（因為它最終對全部元素都進行了調整，算法結束後，整個堆還是一個最小堆）的調優，時間複雜度O（n+k^2）沒有量級的提高，空間複雜度為O（N）也不會減少。

原理了解透了，那麼寫代碼，就不難了，完整粗略代碼如下（有問題煩請批評指正）：

//copyright@泡泡魚
//July、2010.06.02。

//@lingyun310：先對元素數組原地建最小堆，O(n)。然後提取K次，但是每次提取時，
//換到頂部的元素隻需要下移頂多k次就足夠了，下移次數逐次減少。此種方法的複雜度為O（n+k^2）。
#include<stdio.h>
#include<stdlib.h>
#defineMAXLEN123456
#defineK100

//
voidHeapAdjust(intarray[],inti,intLength)
{
intchild,temp;
for(temp=array[i];2*i+1<Length;i=child)
{
child=2*i+1;
if(child<Length-1&&array[child+1]<array[child])
child++;
if(temp>array[child])
array[i]=array[child];
else
break;
array[child]=temp;
}
}

voidSwap(int*a,int*b)
{
*a=*a^*b;
*b=*a^*b;
*a=*a^*b;
}

intGetMin(intarray[],intLength,intk)
{
intmin=array[0];
Swap(&array[0],&array[Length-1]);

intchild,temp;
inti=0,j=k-1;
for(temp=array[0];j>0&&2*i+1<Length;--j,i=child)
{
child=2*i+1;
if(child<Length-1&&array[child+1]<array[child])
child++;
if(temp>array[child])
array[i]=array[child];
else
break;
array[child]=temp;
}

returnmin;
}

voidKmin(intarray[],intLength,intk)
{
for(inti=Length/2-1;i>=0;--i)
//初始建堆，時間複雜度為O(n)
HeapAdjust(array,i,Length);

intj=Length;
for(i=k;i>0;--i,--j)
//k次循環，每次循環的複雜度最多為k次交換，複雜度為o(k^2)
{
intmin=GetMin(array,j,i);
printf("%d,",min);
}
}

intmain()
{
intarray[MAXLEN];
for(inti=MAXLEN;i>0;--i)
array[MAXLEN-i]=i;

Kmin(array,MAXLEN,K);
return0;
}



在算法導論第6章有下面這樣一張圖，因為開始時曾一直糾結過這個問題，“取出堆頂元素之後，把堆中下面的最後一個元素送到堆頂”。因為算法導論上下面這張圖給了我一個假象，從a）->b）中，讓我誤以為是取出堆頂元素之後，是把原來堆頂元素的兒子送到堆頂。而事實上不是這樣的。因為在下面的圖中，16被删除後，堆中最後一個元素1代替16成為根結點，然後1下沉（注意下圖所示的過程是最大堆的堆排序過程，不再是上面的最小堆了，是以小的元素當然要下移），14上移到堆頂。是以，圖中小圖圖b）是已經在小圖a）之和被調整過的最大堆了，隻是調整了logn次，非上面所述的k次。
           

ok，接下來，咱們再着重分析下上述思路4。或許，你不會相信上述思路4的觀點，但我馬上将用事實來論證我的觀點。這幾天，我一直在想，也一直在找資料查找類似快速排序的partition過程的分治算法（即上述在程式設計之美上提到的第4點思路），是否能做到O（N）的論述或證明，

然找了三天，不但在算法導論上找到了RANDOMIZED-SELECT，在平均情況下為線性期望時間O（N）的論證（請參考本文第二節），還在mark allen weiss所著的資料結構與算法分析–C語言描述一書（還得多謝朋友sheguang提醒）中，第7章第7.7.6節（本文下面的第4節末，也有關此問題的闡述）也找到了在最壞情況下，為線性時間O（N）（是的，不含期望，是最壞情況下為O（N））的快速選擇算法（此算法，本文文末，也有闡述），請看下述文字（括号裡的中文解釋為本人添加）：

Quicksort can be modified to solve the selection problem, which we have seen in chapters 1 and 6. Recall that by using a priority queue, we can find the kth largest (or smallest) element in O(n + k log n)（即上述思路7）. For the special case of finding the median, this gives an O(n log n) algorithm.

Since we can sort the file in O(nlog n) time, one might expect to obtain a better time bound for selection. The algorithm we present to find the kth smallest element in a set S is almost identical to quicksort. In fact, the first three steps are the same. We will call this algorithm quickselect（叫做快速選擇）. Let |Si| denote the number of elements in Si（令|Si|為Si中元素的個數）. The steps of quickselect are（快速選擇，即上述程式設計之美一書上的，思路4，步驟如下）:

1. If |S| = 1, then k = 1 and return the elements in S as the answer. If a cutoff for small files is being used and |S| <=CUTOFF, then sort S and return the kth smallest element.
2. Pick a pivot element, v (- S.（選取一個樞紐元v屬于S）
3. Partition S - {v} into S1 and S2, as was done with quicksort.
（将集合S-{v}分割成S1和S2，就像我們在快速排序中所作的那樣）

4. If k <= |S1|, then the kth smallest element must be in S1. In this case, return quickselect (S1, k). If k = 1 + |S1|, then the pivot is the kth smallest element and we can return it as the answer. Otherwise, the kth smallest element lies in S2, and it is the (k - |S1| - 1)st smallest element in S2. We make a recursive call and return quickselect (S2, k - |S1| - 1).
（如果k<=|S1|，那麼第k個最小元素必然在S1中。在這種情況下，傳回quickselect（S1,k）。如果k=1+|S1|，那麼樞紐元素就是第k個最小元素，即找到，直接傳回它。否則，這第k個最小元素就在S2中，即S2中的第（k-|S1|-1）（多謝王洋提醒修正）個最小元素，我們遞歸調用并傳回quickselect（S2，k-|S1|-1））。

In contrast to quicksort, quickselect makes only one recursive call instead of two. The worst case of quickselect is identical to that of quicksort and is O(n2). Intuitively, this is because quicksort's worst case is when one of S1 and S2 is empty; thus, quickselect（快速選擇） is not really saving a recursive call. The average running time, however, is O(n)（不過，其平均運作時間為O（N）。看到了沒，就是平均複雜度為O（N）這句話）. The analysis is similar to quicksort's and is left as an exercise.

The implementation of quickselect is even simpler than the abstract description might imply. The code to do this shown in Figure 7.16. When the algorithm terminates, the kth smallest element is in position k. This destroys the original ordering; if this is not desirable, then a copy must be made.
           

并給出了代碼示例：

//[email protected]
//July、updated，2011.05.05淩晨.

//q_selectplacesthekthsmallestelementina[k]
voidq_select(input_typea[],intk,intleft,intright)
{
inti,j;
input_typepivot;
if(left+CUTOFF<=right)
{
pivot=median3(a,left,right);
//取三數中值作為樞紐元，可以消除最壞情況而保證此算法是O（N）的。不過，這還隻局限在理論意義上。
//稍後，除了下文的第二節的随機選取樞紐元，在第四節末，您将看到另一種選取樞紐元的方法。

i=left;j=right-1;
for(;;)
{
while(a[++i]<pivot);
while(a[--j]>pivot);
if(i<j)
swap(&a[i],&a[j]);
else
break;
}
swap(&a[i],&a[right-1]);/*restorepivot*/
if(k<i)
q_select(a,k,left,i-1);
else
if(k>i)
q-select(a,k,i+1,right);
}
else
insert_sort(a,left,right);
}
           

結論：

與快速排序相比，快速選擇隻做了一次遞歸調用而不是兩次。快速選擇的最壞情況和快速排序的相同，也是O（N^2），最壞情況發生在樞紐元的選取不當，以緻S1，或S2中有一個序列為空。
這就好比快速排序的運作時間與劃分是否對稱有關，劃分的好或對稱，那麼快速排序可達最佳的運作時間O（n*logn），劃分的不好或不對稱，則會有最壞的運作時間為O（N^2）。而樞紐元的選取則完全決定快速排序的partition過程是否劃分對稱。
快速選擇也是一樣，如果樞紐元的選取不當，則依然會有最壞的運作時間為O（N^2）的情況發生。那麼，怎麼避免這個最壞情況的發生，或者說就算是最壞情況下，亦能保證快速選擇的運作時間為O（N）列?對了，關鍵，還是看你的樞紐元怎麼選取。
像上述程式使用三數中值作為樞紐元的方法可以使得最壞情況發生的機率幾乎可以忽略不計。然而，稍後，在本文第四節末，及本文文末，您将看到：通過一種更好的方法，如“五分化中項的中項”，或“中位數的中位數”等方法選取樞紐元，我們将能徹底保證在最壞情況下依然是線性O（N）的複雜度。
           

至于程式設計之美上所述：從數組中随機選取一個數X，把數組劃分為Sa和Sb倆部分，那麼這個問題就轉到了下文第二節RANDOMIZED-SELECT，以線性期望時間做選擇，無論如何，程式設計之美上的解法二的複雜度為O（n*logk）都是有待商榷的。至于最壞情況下一種全新的，為O（N）的快速選擇算法，直接跳轉到本文第四節末，或文末部分吧）。

不過，為了公正起見，把程式設計之美第141頁上的源碼貼出來，由大家來評判：

Kbig(S,k):
if(k<=0):
return[]//傳回空數組
if(lengthS<=k):
returnS
(Sa,Sb)=Partition(S)
returnKbig(Sa,k).Append(Kbig(Sb,k–lengthSa)

Partition(S):
Sa=[]//初始化為空數組
Sb=[]//初始化為空數組
Swap(s[1],S[Random()%lengthS])//随機選擇一個數作為分組标準，以
//避免特殊資料下的算法退化，也可
//以通過對整個資料進行洗牌預處理
//實作這個目的
p=S[1]
foriin[2:lengthS]:
S[i]>p?Sa.Append(S[i]):Sb.Append(S[i])
//将p加入較小的組，可以避免分組失敗，也使分組
//更均勻，提高效率
lengthSa<lengthSb?Sa.Append(p):Sb.Append(p)
return(Sa,Sb)
           

你已經看到，它是随機選取數組中的任一進制素為樞紐的，這就是本文下面的第二節RANDOMIZED-SELECT的問題了，隻是要修正的是，此算法的平均時間複雜度為線性期望O（N）的時間。而，稍後在本文的第四節或本文文末，您還将會看到此問題的進一步闡述（SELECT算法，即快速選擇算法），此SELECT算法能保證即使在最壞情況下，依然是線性O（N）的複雜度。

updated：

1、為了照顧手中沒程式設計之美這本書的friends，我拍了張照片，現貼于下供參考（提醒：1、書上為尋找最大的k個數，而我們面對的問題是尋找最小的k個數，兩種形式，一個本質（該修改的地方，上文已經全部修改）。2、書中描述與上文思路4并無原理性出入，不過，勿被圖中記的筆記所誤導，因為之前也曾被書中的這個n*logk複雜度所誤導過。ok，相信，看完本文後，你不會再有此疑惑）：

2、同時，在程式設計之美原書上此節的解法五的開頭提到，“上面類似快速排序的方法平均時間複雜度是線性的”，我想上面的類似快速排序的方法，應該是指解法（即如上所述的類似快速排序partition過程的方法），但解法二得出的平均時間複雜度卻為O（N*logk），明擺着前後沖突（參見下圖）。

3、此文創作後的幾天，已把本人的意見回報給鄒欣等人，下面是程式設計之美bop1的改版修訂位址的頁面截圖（本人也在參加其改版修訂的工作），下面的文字是我的記錄（同時，本人聲明，此狂想曲系列文章系我個人獨立創作，與其它的事不相幹）：
           

第二節、Randomized-Select，線性期望時間

下面是RANDOMIZED-SELECT(A, p, r)完整僞碼（來自算法導論），我給了注釋，或許能給你點啟示。在下結論之前，我還需要很多的時間去思量，以確定結論之完整與正确。

PARTITION(A, p, r) //partition過程 p為第一個數，r為最後一個數
1 x ← A[r] //以最後一個元素作為主元
2 i ← p - 1
3 for j ← p to r - 1
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] <-> A[j]
7 exchange A[i + 1] <-> A[r]
8 return i + 1

RANDOMIZED-PARTITION(A, p, r) //随機快排的partition過程
1 i ← RANDOM(p, r) //i 随機取p到r中個一個值
2 exchange A[r] <-> A[i] //以随機的 i作為主元
3 return PARTITION(A, p, r) //調用上述原來的partition過程

RANDOMIZED-SELECT(A, p, r, i) //以線性時間做選擇，目的是傳回數組A[p..r]中的第i 小的元素
1 if p = r //p=r，序列中隻有一個元素 
2 then return A[p]
3 q ← RANDOMIZED-PARTITION(A, p, r) //随機選取的元素q作為主元 
4 k ← q - p + 1 //k表示子數組 A[p…q]内的元素個數，處于劃分低區的元素個數加上一個主元元素
5 if i == k //檢查要查找的i 等于子數組中A[p....q]中的元素個數k
6 then return A[q] //則直接傳回A[q] 
7 else if i < k 
8 then return RANDOMIZED-SELECT(A, p, q - 1, i)
//得到的k 大于要查找的i 的大小，則遞歸到低區間A[p，q-1]中去查找
9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)
//得到的k 小于要查找的i 的大小，則遞歸到高區間A[q+1，r]中去查找。
           

寫此文的目的，在于起一個抛磚引玉的作用。希望，能引起你的重視及好的思路，直到有個徹底明白的結果。

updated：算法導論原英文版有關于RANDOMIZED-SELECT(A, p, r)為O（n）的證明。為了一個徹底明白的闡述，我現将其原文的證明自個再翻譯加工後，闡述如下：

此RANDOMIZED-SELECT最壞情況下時間複雜度為Θ(n2),即使是要選擇最小元素也是如此，因為在劃分時可能極不走運，總是按餘下元素中的最大元素進行劃分，而劃分操作需要O（n）的時間。

然而此算法的平均情況性能極好，因為它是随機化的，故沒有哪一種特别的輸入會導緻其最壞情況的發生。

算法導論上，針對此RANDOMIZED-SELECT算法平均時間複雜度為O（n）的證明，引用如下，或許，能給你我多點的啟示（本來想直接引用第二版中文版的翻譯文字，但在中英文對照閱讀的情況下，發現第二版中文版的翻譯實在不怎麼樣，是以，得自己一個一個字的敲，最終敲完修正如下），分4步證明：

1、當RANDOMIZED-SELECT作用于一個含有n個元素的輸入數組A[p ..r]上時，所需時間是一個随機變量，記為T(n),我們可以這樣得到線性期望值E [T(n)]的下界：程式RANDOMIZED-PARTITION會以等同的可能性傳回數組中任何一個元素為主元，是以，對于每一個k，（1 ≤k ≤n）,子數組A[p ..q]有k個元素，它們全部小于或等于主元元素的機率為1/n.對k = 1, 2,...,n,我們定訓示器Xk，為：

Xk = I{子數組A[p ..q]恰有k個元素} ,

我們假定元素的值不同，是以有

E[Xk]=1/n

當調用RANDOMIZED-SELECT并且選擇A[q]作為主元元素的時候,我們事先不知道是否會立即找到我們所想要的第i小的元素，因為，我們很有可能需要在子數組A[p ..q - 1], 或A[q + 1 ..r]上遞歸繼續進行尋找.具體在哪一個子數組上遞歸尋找，視第i小的元素與A[q]的相對位置而定.

2、假設T(n)是單調遞增的，我們可以将遞歸所需時間的界限限定在輸入數組時可能輸入的所需遞歸調用的最大時間（此句話，原中文版的翻譯也是有問題的）.換言之,我們斷定,為得到一個上界，我們假定第i小的元素總是在劃分的較大的一邊，對一個給定的RANDOMIZED-SELECT,訓示器Xk剛好在一個k值上取1，在其它的k值時，都是取0.當Xk =1時，可能要遞歸處理的倆個子數組的大小分别為k-1，和n-k，是以可得到遞歸式為

取期望值為：

為了能應用等式(C.23),我們依賴于Xk和T(max(k - 1,n - k))是獨立的随機變量（這個可以證明，證明此處略）。

3、下面，我們來考慮下表達式max(k - 1,n -k)的結果.我們有：

如果n是偶數，從T(⌉)到T(n - 1)每個項在總和中剛好出現倆次，T(⌋)出現一次。是以，有

我們可以用替換法來解上面的遞歸式。假設對滿足這個遞歸式初始條件的某個常數c，有T(n) ≤cn。我們假設對于小于某個常數c（稍後再來說明如何選取這個常數）的n，有T(n) =O(1)。 同時，還要選擇一個常數a，使得對于所有的n>0，由上式中O(n)項(用來描述這個算法的運作時間中非遞歸的部分)所描述的函數，可由an從上方限界得到（這裡，原中文版的翻譯的确是有點含糊）。利用這個歸納假設，可以得到：

（此段原中文版翻譯有點問題，上述文字已經修正過來，對應的此段原英文為：We solve the recurrence by substitution. Assume thatT(n)≤cn for some constant c that satisfies the initial conditions of the recurrence. We assume thatT(n) =O(1) fornless than some constant; we shall pick this constant later. We also pick a constanta such that the function described by theO(n) term above (which describes the non-recursive component of the running time of the algorithm) is bounded from above byan for alln> 0. Using this inductive hypothesis, we have）

4、為了完成證明，還需要證明對足夠大的n，上面最後一個表達式最大為cn，即要證明：cn/4 -c/2 -an ≥ 0.如果在倆邊加上c/2，并且提取因子n，就可以得到n(c/4 -a) ≥c/2.隻要我們選擇的常數c能滿足c/4 -a > 0, i.e.,即c > 4a,我們就可以将倆邊同時除以c/4 -a, 最終得到：

綜上，如果假設對n < 2c/(c -4a),有T(n) =O(1)，我們就能得到E[T(n)] =O(n)。是以，最終我們可以得出這樣的結論，并确認無疑：在平均情況下，任何順序統計量（特别是中位數）都可以線上性時間内得到。
           

結論：如你所見，RANDOMIZED-SELECT有線性期望時間O（N）的複雜度，但此RANDOMIZED-SELECT算法在最壞情況下有O（N^2）的複雜度。是以，我們得找出一種在最壞情況下也為線性時間的算法。稍後，在本文的第四節末，及本文文末部分，你将看到一種在最壞情況下是線性時間O（N）的複雜度的快速選擇SELECT算法。

第三節、各執己見，百家争鳴

updated ：本文昨晚釋出後，現在朋友們之間，主要有以下幾種觀點（在徹底弄清之前，最好不要下結論）：

luuillu：我不認為随機快排比直接快排的時間複雜度小。使用快排處理資料前，我們是不知道資料的排列規律的，是以一般情況下，被處理的資料本來就是一組随機資料，對于随機資料再多進行一次随機化處理，資料仍然保持随機性，對排序沒有更好的效果。 對一組資料采用随選主元的方法，在極端的情況下，也可能出現每次選出的主元恰好是從大到小排列的，此時時間複雜度為O（n^2）.當然這個機率極低。随機選主元的好處在于，由于在現實中常常需要把一些資料儲存為有序資料，是以，快速排序碰到有序資料的機率就會高一些，使用随機快排可以提高對這些資料的處理效率。這個機率雖然高一些，但仍屬于特殊情況，不影響一般情況的時間複雜度。我覺得樓主上面提到的的思路4和思路5的時間複雜度是一樣的。

571樓 得分：0 Sorehead 回複于：2011-03-09 16:29:58
關于第五題：
Sorehead： 這兩天我總結了一下，有以下方法可以實作：
1、第一次周遊取出最小的元素，第二次周遊取出第二小的元素，依次直到第k次周遊取出第k小的元素。這種方法最簡單，時間複雜度是O(k*n)。看上去效率很差，但當k很小的時候可能是最快的。
2、對這n個元素進行排序，然後取出前k個資料即可，可以采用比較普遍的堆排序或者快速排序，時間複雜度是O(n*logn)。這種方法有着很大的弊端，題目并沒有要求這最小的k個數是排好序的，更沒有要求對其它資料進行排序，對這些資料進行排序某種程度上來講完全是一種浪費。而且當k=1時，時間複雜度依然是O(n*logn)。
3、可以把快速排序改進一下，應該和樓主的kth_elem一樣，這樣的好處是不用對所有資料都進行排序。平均時間複雜度應該是O(n*logk)。（在本文最後一節，你或将看到，複雜度可能應該為O（n））
4、使用我開始講到的平衡二叉樹或紅黑樹，樹隻用來儲存k個資料即可，這樣周遊所有資料隻需要一次。時間複雜度為O(n*logk)。後來我發現這個思路其實可以再改進，使用堆排序中的堆，堆中元素數量為k，這樣堆中最大元素就是頭節點，周遊所有資料時比較次數更少，當然時間複雜度并沒有變化。
5、使用計數排序的方法，建立一個數組，以元素值為該數組下标，數組的值為該元素在數組中出現的次數。這樣周遊一次就可以得到這個數組，然後查詢這個數組就可以得到答案了。時間複雜度為O(n)。如果元素值沒有重複的，還可以使用位圖方式。這種方式有一定局限性，元素必須是正整數，并且取值範圍不能太大，否則就造成極大的空間浪費，同時時間複雜度也未必就是O(n)了。當然可以再次改進，使用一種比較合适的雜湊演算法來代替元素值直接作為數組下标。

litaoye：按照算法導論上所說的，最壞情況下線性時間找第k大的數。證明一下：把數組中的元素，5個分為1組排序，排序需要進行7次比較(2^7 > 5!)，這樣需要1.4 * n次比較，可以完成所有組的排序。取所有組的中位數，形成一個新的數組，有n/5個元素，5個分為1組排序，重複上面的操作，直到隻剩下小于5個元素，找出中位數。根據等比數列求和公式，求出整個過程的比較次數：7/5 + 7/25 + 7/125 +...... = 7/4，用7/4 * n次比較可以找出中位數的中位數M。能夠證明，整個數組中>=M的數超過3*n / 10 - 6，<=M的數超過3*n / 10 - 6。以M為基準，執行上面的PARTITION，每次至少可以淘汰3*n / 10 - 6，約等于3/10 * n個數，也就是說是用(7/4 + 1) * n次比較之後，最壞情況下可以讓資料量變為原來的7/10，同樣根據等比數列求和公式，可以算出最壞情況下找出第k大的數需要的比較次數，1 + 7/10 + 49/100 + .... = 10/3, 10/3 * 11/4 * n = 110/12 * n，也就是說整個過程是O(n)的，盡管隐含的常數比較大 。
           

總結：

關于RANDOMIZED-SELECT(A, q + 1, r, i - k)，期望運作時間為O（n）已經沒有疑問了，更嚴格的論證在上面的第二節也已經給出來了。

ok，現在，咱們剩下的問題是，除了此RANDOMIZED-SELECT(A, q + 1, r, i - k)方法（實用價值并不大）和計數排序，都可以做到O（n）之外，還有類似快速排序的partition過程，是否也能做到O（n）?

第四節、類似partition過程，最壞亦能做到O（n）?

我想，經過上面的各路好漢的思路轟炸，您的頭腦和思維肯定有所混亂了。ok，下面，我盡量以通俗易懂的方式來繼續闡述咱們的問題。上面第三節的總結提出了一個問題，即類似快速排序的partition過程，是否也能做到O（n）?

我們說對n個數進行排序，快速排序的平均時間複雜度為O（n*logn），這個n*logn的時間複雜度是如何得來的列?

經過之前我的有關快速排序的三篇文章，相信您已經明了了以下過程：快速排序每次選取一個主元X，依據這個主元X，每次把整個序列劃分為A，B倆個部分，且有Ax