在浮點數組中最快的選擇最大k個數的演算法是什麼？

---

O(n).為什麼沒人說這個？

被認為是20世紀最經典的十大演算法之一（我也不知道是誰評的，不過應該夠格）

http://people.csail.mit.edu/rivest/BlumFloydPrattRivestTarjan-TimeBoundsForSelection.pdf

Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., Tarjan, R. E. (1973). Time bounds for selection. Journal of computer and system sciences, 7(4), 448-461.

看作者名單就知道多厲害了，5個作者里有4個是圖靈獎得主（Blum 1995, Floyd 1978, Rivest 2002, Tarjan 1986）

---

演算法導論第九章有寫，時間複雜度為O(n)

具體方法為：

1，每次隨機取一個數，用快排的思想定位他為第p大的數

2，比較p與k，如果p小於k則在[p+1,n]上尋找第k-p大的數；如果p大於k，則在[1,p]上尋找第k大的數；如果p等於k，則為解。

具體時間複雜度為什麼是O(n)演算法導論上有詳細證明。

---

三個常見思路

一 排序

二 堆

建堆需要線性時間,找最大需要對數時間,因此

三 找第k元,將數組劃分好(後排序)

找到第k個元素的問題:

1. 快排中的partition 過程有個很好的性質就是它可以確定pivot在最終的排序中的位置,所以可以很容里的根據這個index和k的大小來遞歸求解. 但還是pivot的選擇問題導致最壞情況下,每次partition只能扔掉1個元素,這樣複雜度就是了.加上排序就是.

2. 有嚴格意義的O(n)的演算法,比如特殊化的取中位數的演算法(取第k個是一樣的,前後比例換一下就好)

選擇分割點的時候採用五五一組取中值,所有組的中值裡面再選中值,這個數作為分割的元素.所有元素被分成4塊,右上角(3r+2個)的肯定大於分割元,左下角(3r+2個)的肯定小於分割元,其它兩塊(各2r個)不確定.

特殊化的,取 n=5(2r+1)

,

( 第一項中6是5個元素中尋找中值的最小比較次數.第二項是找中位數裡面的中位數,4r是分割後不確定的兩塊裡面元素個數,最後一項是最差情況的遞歸代價)

可證明這個式子是的.

3. 並且它將數組分為大於它的部分和小於它的部分,也可以結束演算法了.

4. 如果需要有序的k個元素的話,進行排序即可.

---

std::nth_element

nth_element - C++ Reference

quickselect

Quickselect - Wikiwand

找個pivot，數組中大於pivot的放左邊，小於的放右邊，類似quicksort, 然後判斷左右兩邊長度，選擇左右兩邊的一個，遞歸。

quicksort每次左右兩邊都要遞歸，所以複雜度NlogN, 但是quickselect每次只要選一個遞歸

複雜度上 T(N) = N + T(N/2)

概率上是O(N)

default_random_engine g(std::random_device {}());

void quickSelect(double* arr, unsigned int size, unsigned int k)
{
if (size &<= 1) return; std::uniform_int_distribution& d(0, size - 1);
std::swap(arr[0], arr[d(g)]);
unsigned int pivotIdx = 0;
for (unsigned int i = 0; i &< size; i++) { if (arr[i] &> arr[pivotIdx] i &> pivotIdx)
{
swap(arr[pivotIdx + 1], arr[i]);
swap(arr[pivotIdx], arr[pivotIdx + 1]);
pivotIdx++;
}
}
if (pivotIdx &> k)
quickSelect(arr, pivotIdx, k);
else if (pivotIdx &< k) quickSelect(arr + pivotIdx, size - pivotIdx, k - pivotIdx); else return; }

---

前k個數如果不要求順序，就quickselect演算法，要求的話，用大小為k的優先隊列如二叉堆等線性掃描一遍。複雜度的話，前者是O(N)，然而這個O(N)有一定的隨機性，臉好的話就很快，臉黑的話就比較慢了。後者的話是O(NlogK)，不過時間相對很穩定

我覺得我得補充下，後者只是在k小的時候比較好，k大的時候還是推薦用quickselect，pivot的話有很多種方法取，平時自己實現的話隨機或者三點中值的效果就很不錯，stl是三點中值法，話說那個五點中值法穩是穩，但常數太大了

---

1. 計數排序行也不是O(N)的。。

2. 只是找出不排序的話，有個quickselect演算法可以O(N)找出第k大的數，然後再掃一遍原數組即可。。

---

做個K那麼大的最小堆，過一遍。因為K是個常數，所以勉強算是O(N)演算法吧。

---

。。。。。。。。無隨機化quick select @vczh 就算不搞acm 演算法你總該懂幾個吧。。。。

---

樓上說的演算法導論的O(n)演算法是沒有問題的。

此外推薦一篇Knuth的論文，該論文第三節對這個問題做了詳盡的複雜度分析。

Knuth D E. Mathematical Analysis of Algorithms,[J]. Proceedings of the Ifip Congress, 1971:19-27.

---

把快排改一改，因為k是已知的，所以可以只排包含k的那個區間。最後的複雜度是n*lb(k)，全是n吧。

---

「劃分樹是一種基於線段樹的。主要用於快速求出(在log(n)的時間複雜度內）序列區間的第k大值」 ———— 百度百科（劃分樹）

求n個數時間複雜度是nlogn

---

推薦閱讀：