去年寫了一篇對快排進行改進的算法，可以在時間復雜度 $O(n)$的情況下，找到第$k$小的數字。

那時候，我還不知道這個算法叫BFPRT算法——現在知道了，還知道它又被稱為中位數的中位數算法，它的最壞時間復雜度為$O(n)$ ，它是由Blum、Floyd、Pratt、Rivest、Tarjan提出，它的思想是修改快速選擇算法的主元選取方法，提高算法在最壞情況下的時間復雜度。

1 STL std::nth_element

而且，我還發現了STL中有一個類似的函數——std::nth_element （位于頭文件<algorithm>中）:
http://www.cplusplus.com/reference/algorithm/nth_element/

#include <iostream> #include <vector> #include <algorithm> #include <functional>int main() {std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());std::cout << "The median is " << v[v.size()/2] << '\n';std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());std::cout << "The second largest element is " << v[1] << '\n'; }

運行結果：
The median is 5
The second largest element is 7

2 BFPRT算法(中位數的中位數算法)

好了，言歸正傳。BFPRT算法主要由兩部分組成（快排、基準選取函數）。基準選取函數也就是中位數的中位數算法（Median of Medians algorithm）的實現，具體來說——就是將快排中基準選取策略進行了優化，改為每次盡可能的選擇中位數作為基準。

那么是如何盡可能的選出中位數？ 如果要找到一個精確的中位數，所消耗的時間代價將得不償失，而且對于快排算法來說，只要基準盡可能的接近真正的中位數，就能形成近似的均分。我在上一篇文章中舉了個例子，這里我再重復一遍：

2.1 舉個例子

假設，我們要找arr[18]的近似中位數——其實，也就是找到數字8。（注意到，由于使用了分組，這里產生的只是盡可能的中位數）

int arr[18] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };

BFPRT算法規定了，將5個元素作為一組（選出中位數）。然后，再選出中位數中的中位數…一直到，最終選出一個數字。

那么，第一輪就是這樣（將選出的中位數放置在最前面）：

//執行momedians之前 { 1,2,3,4,5} {6,7,8,9,10} {11,12,13,14,15} {16,17,18 };

分別對每組sort后選取小組中位數，再使用swap將小組中位數放置在“最前面”對應位置（注意下文中*號的標注，它表示這一步選出的小組中位數放置到哪兒去了）。

//開始momedians { 3*,2,1*,4,5};//sort->swap(3,1) { 3,8*,1,4,5} {6,7,2*,9,10};//sort->swap(8,2) { 3,8,13*,4,5} {6,7,2,9,10} {11,12,1*,14,15};//sort->swap(13,1) { 3,8,13,17*,5} {6,7,2,9,10} {11,12,1,14,15} {16,4*,18 };//sort->swap(17,4)

同樣，第二輪初始時就成如下樣子了，很顯然已經少于5個數字了：

//執行momedians之前 { 3,8,13,17};

2.2 算法實現(c++)

可以將上述過程使用C++代碼描述如下（對于5個數字的排序，使用Insert sort可能會效率更高）。再次強調，下面這段代碼唯一的作用，就是用來選出每次快排的基準：

//Median of Medians algorithm int momedians(int* const low, int* const high) {if (low >= high - 1) {return *low;}//int grp_length = (int)std::sqrt(high - low);int grp_length = 5, grp_idx = 0;for (int* l = low, *r; l < high; l = r+1) {r = (l + grp_length >= high) ? high : l + grp_length - 1;std::sort(l, r); //可以使用下文的void isort(int* const low, int* const high)std::swap(*(low+grp_idx++), *(l + (r - l) / 2));}return momedians(low, low + grp_idx); }

寫到這里已經將BFPRT算法核心介紹完畢了。

如果想測試使用Insert sort是否會帶來效率上提升的小伙伴，可以試試下面這段代碼insert_sort，嘗試著替換文中的std::sort排序函數。

//Insert sort void insert_sort(int* const low, int* const high) {for (int* i = low + 1; i <= high; ++i) {if (*i < *(i-1)) {int border = *i, *j = i-1;for ( ; border < *j; --j) {*(j+1) = *j;}*(j+1) = border;}} }

讓我們思維次再回到momedians函數。從上述代碼中可以看到grp_length = 5是一個固定值。那么，在BFPRT算法中，為什么是選5個作為分組？ 這個我也不是很明白，我也嘗試使用sqrt(數組長度)作為分組的長度。

有興趣的可以閱讀 ACdreamer 的一篇《BFPRT算法原理》，他在文章結尾處，對為什么使用5作為固定分組長度進行了簡單說明。同時，還附有BFPRT算法的最壞時間復雜度為$O(n)$ 的證明。

好了，以下為完整的“BFPRT算法：時間復雜度$O(n)$求第k小的數字”代碼。如上文所說，算法主體功能是快排，只是在基準選取的時候使用了momedians算法——而不是直接取第一個數作為基準（嚴蔚敏版教材中的做法）。

#include <iostream> #include <algorithm> using namespace std;//Median of Medians algorithm int momedians(int* const low, int* const high) {if (low >= high - 1) {return *low;}int grp_length = 5, grp_idx = 0;for (int* l = low, *r; l < high; l = r+1) {r = (l + grp_length >= high) ? high : l + grp_length - 1;std::sort(l, r);std::swap(*(low+grp_idx++), *(l + (r - l) / 2));}return momedians(low, low + grp_idx); }//Quick sort int qsort(int* const low, int* const high, int* const ptrk) {int* l = low, *r = high;if (l < r) {int pivot = momedians(l, r);while (l < r) {while (l < r && *r >= pivot) {--r;}*l = *r;while (l < r && *l <= pivot) {++l;}*r = *l;}*r = pivot;}//per qsort end, check left == right == ptrk?return r == ptrk ? *ptrk :(r > ptrk ?qsort(low, r - 1, ptrk) :qsort(r + 1, high, ptrk)); }//Blum、Floyd、Pratt、Rivest、Tarjan int bfprt(int* const low, int* const high, const int k = 1) {if (low >= high || k < 1 || k > high - low) {throw std::invalid_argument("low > high || k < 1");}return qsort(low, high-1, low + k -1);//[low, high) }int main() {int arr[18] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };//cout << bfprt(&arr[0], &arr[0]+1, 1) << endl;cout << bfprt(&arr[0], &arr[0] + 18, 18) << endl;return 0; }

以上的代碼是針對int數組編寫的，下面再測試一下對于其他類型的支持情況（這里直接粗暴的加上了一個模板）。有一點想強調的是，這里的bfprt函數參數是左閉右開區間[low,high)，同時k必須是從1開始的正數。

//Blum、Floyd、Pratt、Rivest、Tarjan template<typename T> T bfprt(T* const low, T* const high, const int k = 1) {if (low >= high || k < 1 || k > high - low) {throw std::invalid_argument("low > high || k < 1");}return qsort(low, high-1, low + k -1);//[low, high) }

在main函數中對int、char、string類型進行了測試。完整代碼如下…

#include <iostream> #include <algorithm> using namespace std;//Median of Medians algorithm template<typename T> T momedians(T* const low, T* const high) {if (low >= high - 1) {return *low;}int grp_length = 5, grp_idx = 0;for (T* l = low, *r; l < high; l = r+1) {r = (l + grp_length >= high) ? high : l + grp_length - 1;std::sort(l, r);std::swap(*(low+grp_idx++), *(l + (r - l) / 2));}return momedians(low, low + grp_idx); }//Quick sort template<typename T> T qsort(T* const low, T* const high, T* const ptrk) {T* l = low, *r = high;if (l < r) {T pivot = momedians(l, r);while (l < r) {while (l < r && *r >= pivot) {--r;}*l = *r;while (l < r && *l <= pivot) {++l;}*r = *l;}*r = pivot;}//per qsort end, check left == right == ptrk?return r == ptrk ? *ptrk :(r > ptrk ?qsort(low, r - 1, ptrk) :qsort(r + 1, high, ptrk)); }//Blum、Floyd、Pratt、Rivest、Tarjan template<typename T> T bfprt(T* const low, T* const high, const int k = 1) {if (low >= high || k < 1 || k > high - low) {throw std::invalid_argument("low > high || k < 1");}return qsort(low, high-1, low + k -1);//[low, high) }int main() {int arr[18] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };cout << bfprt(&arr[0], &arr[0] + 18, 18) << endl;char str[7] = {'a','b','c','d','e','f','g'};cout << bfprt(&str[0], &str[0] + 7, 4) << endl;string s = "abcdefghijklmnopqrstuvwxyz";cout << bfprt(&s[0], &s[0] + 26, 10) << endl;return 0; }

總結

以上是生活随笔為你收集整理的【最详细】BFPRT算法：时间复杂度O(n)求第k小的数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。