BFPRT(線性查找算法)
BFPRT 算法解決的問題十分經典，即從某 n 個元素的序列中選出第 k 大（第 k 小）
的元素，通過巧妙的分析，BFPRT 可以保證在最壞情況下仍為線性時間複雜度。
該算法的思想與快速排序思想相似，當然，為使得算法在最壞情況下，依然能達
到 o(n)的時間複雜度，五位算法作者做了精妙的處理
算法步驟：
1. 将 n 個元素每5個一組，分成 n/5(上界)組。
2. 取出每一組的中位數，任意排序方法，比如插入排序。
3. 遞歸的調用 selection 算法查找上一步中所有中位數的中位數，設為 x，偶
數個中位數的情況下設定為選取中間小的一個。
4. 用 x 來分割數組，設小于等于 x 的個數為 k，大于 x 的個數即為 n-k。
5. 若 i==k，傳回 x；若 i<k，在小于 x 的元素中遞歸查找第 i 小的元素；若 i>k，
在大于 x 的元素中遞歸查找第 i-k 小的元素。
終止條件：n=1時，傳回的即是 i 小元素
尋找最小的 k 個數
題目描述
輸入 n 個整數，輸出其中最小的 k 個。
分析與解法
解法一
要求一個序列中最小的 k 個數，按照慣有的思維方式，則是先對這個序列從小到
大排序，然後輸出前面的最小的 k 個數。
至于選取什麼的排序方法，我想你可能會第一時間想到快速排序（我們知道，快
速排序平均所費時間為 n*logn ），然後再周遊序列中前 k 個元素輸出即可。
是以，總的時間複雜度： O（n * log n)+O(k)=O（n * log n） 。
解法二
咱們再進一步想想，題目沒有要求最小的 k 個數有序，也沒要求最後 n-k 個數有
序。既然如此，就沒有必要對所有元素進行排序。這時，咱們想到了用選擇或交
換排序，即：
1、周遊 n 個數，把最先周遊到的 k 個數存入到大小為 k 的數組中，假設它們即
是最小的 k 個數；
2、對這 k 個數，利用選擇或交換排序找到這 k 個元素中的最大值 kmax（找最大
值需要周遊這 k 個數，時間複雜度為 O（k） ）；
3、繼續周遊剩餘 n-k 個數。假設每一次周遊到的新的元素的值為 x，把 x 與 kmax
比較：如果 x < kmax ，用 x 替換 kmax，并回到第二步重新找出 k 個元素的
數組中最大元素 kmax‘；如果 x >= kmax ，則繼續周遊不更新數組。
每次周遊，更新或不更新數組的所用的時間為 O（k） 或 O（0） 。故整趟
下來，時間複雜度為 n*O（k）=O（n*k）
解法三
更好的辦法是維護容量為 k 的最大堆，原理跟解法二的方法相似：
1、用容量為 k 的最大堆存儲最先周遊到的 k 個數，同樣假設它們即是最
小的 k 個數；
2、堆中元素是有序的，令 k1<k2<...<kmax（kmax 設為最大堆中的最大元
素）
3、周遊剩餘 n-k 個數。假設每一次周遊到的新的元素的值為 x，把 x 與
堆頂元素 kmax 比較：如果 x < kmax ，用 x 替換 kmax，然後更新堆（用
時 logk）；否則不更新堆。
這樣下來，總的時間複雜度: O（k+（n-k）*logk）=O（n*logk） 。此方法得
益于堆中進行查找和更新的時間複雜度均為： O(logk) （若使用解法二：在數
組中找出最大元素，時間複雜度： O（k））
解法四
在《資料結構與算法分析--c 語言描述》一書，第7章第7.7.6節中，闡述了一種
在平均情況下，時間複雜度為 O（N） 的快速選擇算法。如下述文字：
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（ 步驟如下 ）:
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.
Pick a pivot element, v (- S.（選取 S 中一個元素作為樞紐元 v）
Partition S - {v} into S1 and S2, as was done with quicksort. （将
集合 S-{v}分割成 S1和 S2，就像快速排序那樣）
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） ）. The analysis is similar to
quicksort's and is left as an exercise.
示例代碼
//QuickSelect 将第 k 小的元素放在 a[k-1]
void QuickSelect( int a[], int k, int left, int right )
{
int i, j;
int pivot;
if( left + cutoff <= right )
{
pivot = median3( a, left, right );
// 取三數中值作為樞紐元，可以很大程度上避免最壞情況
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 ] );
if( k <= i )
QuickSelect( a, k, left, i - 1 );
else if( k > i + 1 )
QuickSelect( a, k, i + 1, right );
}
else
InsertSort( a + left, right - left + 1 );
}
這個快速選擇 SELECT 算法，類似快速排序的劃分方法。N 個數存儲在數組 S 中，
再從數組中選取“中位數的中位數”作為樞紐元 X，把數組劃分為 Sa 和 Sb 倆部
分，Sa<=X<=Sb，如果要查找的 k 個元素小于 Sa 的元素個數，則傳回 Sa 中較小
的 k 個元素，否則傳回 Sa 中所有元素+Sb 中小的 k-|Sa|個元素，這種解法在平
均情況下能做到 O（N） 的複雜度
解法五
《算法導論》介紹了一個随機選取主元的選擇算法 RANDOMIZED-SELECT。它每次
都是随機選取數列中的一個元素作為主元，在 O（n） 的時間内找到第 k 小的
元素，然後周遊輸出前面的 k 個小的元素。平均時間複雜度： O（n+k）=O（n）
（當 k 比較小時）。
我們知道，快速排序是以固定的第一個或最後一個元素作為主元，每次遞歸劃分
都是不均等的，最後的平均時間複雜度為： O（n*logn）。而 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] 中
去查找。
下面則是《算法導論》原版關于 RANDOMIZED-SELECT(A, p, r)為 O（n） 的
證明，闡述如下：
此 RANDOMIZED-SELECT 最壞情況下時間複雜度為Θ(n2),即使是要選擇最小元素
也是如此，因為在劃分時可能極不走運，總是按餘下元素中的最大元素進行劃分，
而劃分操作需要 O（n）的時間。
然而此算法的平均情況性能極好，因為它是随機化的，故沒有哪一種特别的輸入
會導緻其最壞情況的發生。
算法導論上，針對此
RANDOMIZED-SELECT 算法平均時間複雜度為 O（ n ）的證明 ，
引用如下，或許，能給你我多點的啟示（本來想直接引用第二版中文版的翻譯文
字，但在中英文對照閱讀的情況下，發現第二版中文版的翻譯實在不怎麼樣，所
以，得自己一個一個字的敲，最終敲完修正如下），分4步證明：
當 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,我們定訓示器 X k ，
為：
X k = I{子數組 A[p ..q]恰有 k 個元素} ,
我們假定元素的值不同，是以有
E[X k ]=1/n
當調用RANDOMIZED-SELECT并且選擇 A[q]作為主元元素的時候,我們事先不知道
是否會立即找到我們所想要的第 i 小的元素，因為，我們很有可能需要在子數組
A[p ..q - 1], 或 A[q + 1 ..r]上遞歸繼續進行尋找.具體在哪一個子數組上遞
歸尋找，視第 i 小的元素與 A[q]的相對位置而定.
假設 T(n)是單調遞增的，我們可以将遞歸所需時間的界限限定在輸入數組時可
能輸入的所需遞歸調用的最大時間（此句話，原中文版的翻譯也是有問題的）.
換言之,我們斷定,為得到一個上界，我們假定第 i 小的元素總是在劃分的較大的
一邊，對一個給定的 RANDOMIZED-SELECT,訓示器 Xk 剛好在一個 k 值上取1，在
其它的 k 值時，都是取0.當 Xk =1時，可能要遞歸處理的倆個子數組的大小分别
為 k-1，和 n-k，是以可得到遞歸式為
取期望值為
為了能應用等式
(C.23)
,我們依賴于 X k 和 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 從上方限界得到（這裡，原中文版的翻譯的确是有點含糊）。利用
這個歸納假設，可以得到
為了完成證明，還需要證明對足夠大的 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） ，但它在最壞情況下時間
的複雜度為 O（N^2）
解法五
《算法導論》第九章第9.3節介紹了一個最壞情況線性時間的選擇算法，如下：
9.3 Selection in worst-case linear time（
最壞情況下線性時間的選擇算法
）
We now examine a selection algorithm whose running time isO(n) in the worst
case（現在來看，一個最壞情況運作時間為 O（N）的選擇算法 SELECT）. Like
RANDOMIZED-SELECT, the algorithm SELECT finds the desired element by
recursively partitioning the input array. The idea behind the algorithm,
however, is toguarantee a good split when the array is partitioned. SELECT
uses the deterministic partitioning algorithm PARTITION from quicksort
(seeSection 7.1), modified to take the element to partition around as an
input parameter（像 RANDOMIZED-SELECT 一樣，SELECTT 通過輸入數組的遞歸
劃分來找出所求元素，但是，該算法的基本思想是要保證對數組的劃分是個好的
劃分。SECLECT 采用了取自快速排序的确定性劃分算法 partition，并做了修改，
把劃分主元元素作為其參數）.
The SELECT algorithm determines theith smallest of an input array ofn >
1 elements by executing the following steps. (Ifn = 1, then SELECT merely
returns its only input value as theith smallest.)（算法 SELECT 通過執行
下列步驟來确定一個有 n>1個元素的輸入數組中的第 i 小的元素。 （如果 n=1，則
SELECT 傳回它的唯一輸入數值作為第 i 個最小值。））
Divide then elements of the input array into⌋ groups of 5 elements
each and at most one group made up of the remainingn mod 5 elements.
Find the median of each of the⌉ groups by first insertion sorting
the elements of each group (of which there are at most 5) and then
picking the median from the sorted list of group elements. Use SELECT recursively to find the medianx of the⌉ medians found
in step 2. (If there are an even number of medians, then by our
convention,x is the lower median.)
Partition the input array around the median-of-mediansx using the
modified version of PARTITION. Letk be one more than the number of
elements on the low side of the partition, so thatx is thekth smallest
element and there aren-k elements on the high side of the partition.
（利用修改過的 partition 過程，按中位數的中位數 x 對輸入數組進行劃分，
讓 k 比劃低去的元素數目多1，是以，x 是第 k 小的元素，并且有 n-k 個元素
在劃分的高區）
Ifi =k, then returnx. Otherwise, use SELECT recursively to find
theith smallest element on the low side ifi k.（ 如果要找的第 i 小的
元素等于程式傳回的 k ，即 i=k，則傳回 x。否則，如果 ik，則在高區間找
第（i-k）個最小元素）
（以上五個步驟，即本文上面的第四節末中所提到的所謂“五分化中項的中項”
的方法。）
To analyze the running time of SELECT, we first determine a lower bound
on the number of elements that are greater than the partitioning element
x. （為了分析 SELECT 的運作時間，先來确定大于劃分主元元素 x 的的元素數的
一個下界）Figure 9.1 is helpful in visualizing this bookkeeping. At least
half of the medians found in step 2 are greater than[1] the median-of-medians x. Thus, at least half of the ⌉ groupscontribute 3
elements that are greater than x, except for the one group that has fewer
than 5 elements if 5 does not dividen exactly, and the one group
containingx itself. Discounting these two groups, it follows that the
number of elements greater thanx is at least
（Figure 9.1: 對上圖的解釋或稱對 SELECT 算法的分析：n 個元素由小圓圈來
表示，并且每一個組占一縱列。組的中位數用白色表示，而各中位數的中位數 x
也被标出。 （當尋找偶數數目元素的中位數時，使用下中位數）。箭頭從比較大的
元素指向較小的元素，從中可以看出，在 x 的右邊，每一個包含5個元素的組中
都有3個元素大于 x，在 x 的左邊，每一個包含5個元素的組中有3個元素小于 x。
大于 x 的元素以陰影背景表示。 ）
Similarly, the number of elements that are less thanx is at least 3n/10
- 6. Thus, in the worst case, SELECT is called recursively on at most 7n/10
+ 6 elements in step 5.
We can now develop a recurrence for the worst-case running timeT(n) of
the algorithm SELECT. Steps 1, 2, and 4 take O(n) time. (Step 2 consists ofO(n) calls of insertion sort on sets of sizeO(1).) Step 3 takes timeT(⌉ ),
and step 5 takes time at mostT(7n/10+ 6), assuming thatT is monotonically
increasing. We make the assumption, which seems unmotivated at first, that
any input of 140 or fewer elements requiresO(1) time; the origin of the
magic constant 140 will be clear shortly. We can therefore obtain the
recurrence
We show that the running time is linear by substitution. More specifically,
we will show thatT(n) ≤cn for some suitably large constant c and alln
> 0. We begin by assuming thatT(n) ≤cn for some suitably large constantc
and alln ≤ 140; this assumption holds ifc is large enough. 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 above byan for alln > 0. Substituting this inductive hypothesis
into the right-hand side of the recurrence yields
T(n) ≤ c⌉ +c(7n/10 + 6) +an
≤ cn/5 +c + 7cn/10 + 6c +an
= 9cn/10 + 7c +an
= cn + (-cn/10 + 7c +an)
which is at mostcn if
Inequality (9.2) is equivalent to the inequalityc ≥ 10a(n/(n - 70)) when
n > 70. Because we assume thatn ≥ 140, we have n/(n - 70) ≤ 2, and so
choosing c ≥ 20a will satisfyinequality (9.2). (Note that there is
nothing special about the constant 140; we could replace it by any integer
strictly greater than 70 and then choosec accordingly.) The worst-case
running time of SELECT is therefore linear（ 是以，此 SELECT 的最壞情況
的運作時間是線性的 ）.
As in a comparison sort (seeSection 8.1), SELECT and RANDOMIZED-SELECT
determine information about the relative order of elements only by
comparing elements. Recall fromChapter 8 that sorting requiresΩ(n lgn)
time in the comparison model, even on average (see Problem 8-1). The
linear-time sorting algorithms in Chapter 8 make assumptions about the
input. In contrast, the linear-time selection algorithms in this chapter
do not require any assumptions about the input. They are not subject to
the Ω(n lgn) lower bound because they manage to solve the selection
problem without sorting.
（與比較排序（算法導論8.1節）中的一樣，SELECT 和 RANDOMIZED-SELECT 僅通
過元素間的比較來确定它們之間的相對次序。在算法導論第8章中，我們知道在
比較模型中，即使在平均情況下，排序仍然要 O（n*logn） 的時間。第8章得
線性時間排序算法在輸入上做了假設。 相反地，本節提到的此類似 partition
過程的 SELECT 算法不需要關于輸入的任何假設，它們不受下界 O（n*logn） 的
限制，因為它們沒有使用排序就解決了選擇問題 （看到了沒，道出了此算法的
本質阿））
Thus, the running time is linear because these algorithms do not sort;
the linear-time behavior is not a result of assumptions about the input,
as was the case for the sorting algorithms inChapter 8. Sorting requires
Ω(n lgn) time in the comparison model, even on average (see Problem 8-1),
and thus the method of sorting and indexing presented in the introduction
to this chapter is asymptotically inefficient.（是以，本節中的選擇算法
之是以具有線性運作時間，是因為這些算法沒有進行排序；線性時間的結論并不
需要在輸入上所任何假設，即可得到）
舉一反三
1、谷歌面試題：輸入是兩個整數數組，他們任意兩個數的和又可以組成一個數
組，求這個和中前 k 個數怎麼做？
分析：
“假設兩個整數數組為 A 和 B，各有 N 個元素，任意兩個數的群組成的數組 C 有
N^2個元素。
那麼可以把這些和看成 N 個有序數列：
A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=…
A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=… …
A[N]+B[1] <= A[N]+B[2] <= A[N]+B[3] <=…
問題轉變成，在這 N^2個有序數列裡，找到前 k 小的元素”
2、有兩個序列 A 和 B,A=(a1,a2,...,ak),B=(b1,b2,...,bk)，A 和 B 都按升序排
列。對于1<=i,j<=k，求 k 個最小的（ai+bj）。要求算法盡量高效。
3、給定一個數列 a1,a2,a3,...,an 和 m 個三元組表示的查詢，對于每個查詢(i，
j，k)，輸出 ai，ai+1，...，aj 的升序排列中第 k 個數。
尋找最小(最大)的 k 個數
題目描述：輸入 n 個整數，輸出其中最小的 k 個元素。
例如：輸入1，2，3，4，5，6，7，8這8個數字，則最小的4個數字為1，2，3，4。
思路1：最容易想到的方法：先對這個序列從小到大排序，然後輸出前面的最小
的 k 個數即可。如果選擇快速排序法來進行排序，則時間複雜度：O（n*logn）
思路2：在思路1的基礎上更進一步想想，題目并沒有要求要查找的 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‘；如果 x>kmax，則不更新數組。這樣，每次更新或不更新數組的所用
的時間為 O（k）或 O（0），整趟下來，總的時間複雜度平均下來為：n*O（k）=O
（n*k）
思路3：與思路2方法類似，隻是用容量為 k 的最大堆取代思路2中數組的作用（從
數組中找最大數需要 O(k)次查找，而從更新一個堆使之成為最大堆隻需要
O(logk)次操作）。具體做法如下：用容量為 k 的最大堆存儲最先周遊到的 k 個數，
并假設它們即是最小的 k 個數，建堆費時 O（k）後，有 k1<k2<…<kmax（kmax
設為大頂堆中最大元素）。繼續周遊數列，每次周遊一個元素 x，與堆頂元素比
較，x<kmax，更新堆（用時 logk），否則不更新堆。這樣下來，總費時 O（k+（n-k）
*logk）=O（n*logk）。
思路4：按程式設計之美中給出的描述，類似快速排序的劃分方法，N 個數存儲在數
組 S 中，再從數組中随機選取一個數 X（随機選取樞紐元，可做到線性期望時間
O（N）的複雜度），把數組劃分為 Sa 和 Sb 倆部分，Sa<=X<=Sb，如果要查找的 k
個元素小于 Sa 的元素個數，則傳回 Sa 中較小的 k 個元素，否則傳回 Sa 中所有
元素+Sb 中小的 k-|Sa|個元素。像上述過程一樣，這個運用類似快速排序的
partition 的快速選擇 SELECT 算法尋找最小的 k 個元素，在最壞情況下亦能做
到 O（N）的複雜度。oh，太酷了，有沒有！
思路5：仍然用到資料結構：堆。具體做法為：針對整個數組序列建最小堆，建
堆所用時間為O（n），然後取堆中的前k 個數，總的時間複雜度即為： O （n+k*logn）。
思路6：與上述思路5類似，不同的是在對元素數組原地建最小堆 O(n)後，然後
提取 K 次，但是每次提取時，換到頂部的元素隻需要下移頂多 k 次就足夠了，下
移次數逐次減少（ 而上述思路 5 每次提取都需要 logn ，是以提取 k 次，思路 7 需
要 k*logn 。 而本思路隻需要 K^2 ）。此種方法的複雜度為 O(n+k^2)。此方法可能
不太直覺，一個更直覺的了解是：每次取出堆頂元素後，最小堆的性質被破壞了，
我們需要調整最小堆使之滿足最小堆的性質。由于我們隻需要求取前 k 個數，我
們無需将整個堆都完整的調整好，隻需保證堆的最上面 k 個數是最小的就可以，
即第一趟調整保持第0層到第 k 層是最小堆，第二趟調整保持第0層到第 k-1層是
最小堆…，依次類推。
在編碼實作上述思路之前，你可能需要了解：快速排序、堆排序
思路3的一個實作：
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#define PARENT(i) (i)/2
#define LEFT(i) 2*(i)+1
#define RIGHT(i) 2*(i+1)
void swap(int *a,int *b)
{
*a=*a^*b; *b=*a^*b; *a=*a^*b
; }
void max_heapify(int *arr,int index,int len)
{
int l=LEFT(index);
int r=RIGHT(index);
int largest;
if(l<len && arr[l]>arr[index])
largest=l; else largest=index;
if(r<len && arr[r]>arr[largest])
largest=r;
if(largest != index){//将最大元素提升，并遞歸
swap(&arr[largest],&arr[index]);
max_heapify(arr,largest,len); }
}
void build_maxheap(int *arr,int len)
{
int i;
if(arr==NULL || len<=1)
return;
for(i=len/2+1;i>=0;--i)
max_heapify(arr,i,len);
}
void k_min(int *arr,int len,int k)
{
int i;
build_maxheap(arr,k);
for (i = k;i < len;i++)
{
if (arr[i] < arr[0])
{
arr[0] = arr[i];
max_heapify(arr,0,k);
}
}
}
int main()
{
int arr[10]={91,8,6,82,15,18,7,46,29,12};
int i;
k_min(arr,10,4); for(i=0;i<10;++i)
printf("%d ",arr[i]); system("pause");
}
for(i=len-1;i>=1;--i){ swap(&arr[0],&arr[i]); max_heapify(arr,0,--len); }
}
思路4的實作
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)
一個簡化實作的如下：
#include <stdio.h>
#include <stdlib.h>
void swap(int *a,int *b)
{
*a=*a^*b; *b=*a^*b; *a=*a^*b;
}
int k_big(int arr[],int low,int high,int k)
{
int pivot = arr[low];
int high_tmp = high;
int low_tmp = low; while(low < high){ //從右向左查找，直到找到第一個小于樞紐元素為止
while (low < high && arr[high] >= pivot)
{
--high;
}
arr[low] = arr[high]; //從左向右查找，直到找到第一個大于樞紐元素為止
while (low < high && arr[low] <= pivot)
{
++low;
} arr[high] = arr[low];
}
arr[low] = pivot;
if (low == k - 1)
{
return arr[low];
}
else if(low > k - 1)
{
return k_big(arr,low_tmp,low-1,k);
}
else {
return k_big(arr,low+1,high_tmp,k);
}
}
int main()
{
int arr[10]={-91,0,6,82,15,18,7,46,-29,12};
int i;
k_big(arr,0,9,4);
for(i=0;i<10;++i)
printf("%d ",arr[i]); system("pause");
}