一個n個元素組成的集合中，第K個順序統計量（Order Statistic）指的是該集合中第K小的元素，我們這里要討論的是如何在線性時間（linear time）里找出一個數組的第K個順序統計量。該問題的算法對于C++程序員來說有一定的借鑒價值。具體如下：

一、問題描述：

問題：給定一個含有n個元素的無序數組，找出第k小的元素。

k = 1 ：最小值
k = n ：最大值
k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ ：中位數

找最大值或最小值很簡單，只需要遍歷一次數組并記錄下最大值或最小值就可以了。我們在這里要解決的問題是一般性的選擇問題。

一種原始的解決方案是，用堆排序或歸并排序將輸入數據進行排序，然后返回第k個元素。這樣在Θ(nlgn)時間內一定可以解決。但是我們希望有更好的方案，最好是線性時間。

二、期望線性時間的解決方案：

為了在線性時間內解決這個選擇問題，我們使用一個隨機的分治算法，即RANDOMIZED-SELECT算法。此算法是使用隨機化的快速排序中的隨機劃分子程序，對輸入數組進行隨機劃分操作，然后判斷第k小元素在劃分后的哪個區域，對所在區域進行遞歸劃分，最后找到第k小元素。

偽代碼如下：

RANDOMIZED-SELECT(A,p,q,i) // i-th smallest in A[p..q]   if p = q     then return A[p]   r = RANDOMIZED-PARTITION(A, p, q)   k = r-p+1  // A[r] is k-th smallest   if i=k     then return A[r]   if i<k     then return RANDOMIZED-SELECT(A, p, r-1, i)   else     then return RANDOMIZED-SELECT(A, r+1, q, i-k) 

這里的RANDOMIZED-PARTITION()是隨機版的劃分操作（快速排序的分析與優化），可見本算法是一個隨機算法，它的期望時間是Θ(n)（假設元素的值是不同的）。

1、Lucky-Case：最好的情況是在正中劃分，劃分的右邊和右邊的元素數量相等，但是1/10和9/10的劃分也幾乎一樣好?？梢赃@么說，任何常數比例的劃分都和1/2:1/2的劃分一樣好。這里以1/10和9/10的劃分為例，算法運行時間遞歸式為T(n) <= T(9n/10) + Θ(n)，根據主定理得到T(n) <= Θ(n)。

2、Unlucky-Case：雖然主元的選取是隨機的，但是如果你運氣足夠差，每次都得到0：n-1的劃分，這就是最壞的情況。此時遞歸式為T(n) = T(n-1) + Θ(n)，則時間復雜度為T(n) = Θ(n^2)。

3、Expected-Time：期望運行時間為Θ(n)，即線性時間。這里就不證明了，證明需要用到指示器隨機變量。

C++代碼如下：

/*************************************************************************   > File Name: RandomizedSelect.cpp   > Author: SongLee  ************************************************************************/ #include<iostream> #include<cstdlib> // srand rand using namespace std;  void swap(int &a, int &b) {   int tmp = a;   a = b;   b = tmp; }  int Partition(int A[], int low, int high) {   int pivot = A[low];   int i = low;   for(int j=low+1; j<=high; ++j)   {     if(A[j] <= pivot)     {       ++i;       swap(A[i], A[j]);     }   }   swap(A[i], A[low]);   return i; }  int Randomized_Partition(int A[], int low, int high) {   srand(time(NULL));   int i = rand() % (high+1);   swap(A[low], A[i]);   return Partition(A, low, high); }  int Randomized_Select(int A[], int p, int q, int i) {   if(p == q)     return A[p];   int r = Randomized_Partition(A, p, q);   int k = r-p+1;   if(i == k)     return A[r];   if(i < k)     return Randomized_Select(A, p, r-1, i);   else     return Randomized_Select(A, r+1, q, i-k); }  /* 測試 */ int main() {   int A[] = {6,10,13,5,8,3,2,11};   int i = 7;   int result = Randomized_Select(A, 0, 7, i);   cout << "The " << i << "th smallest element is " << result << endl;   return 0; } 

三、最壞情況線性時間的解決方案

雖然最壞情況Θ(n2)出現的概率非常非常小，但是不代表它不會出現。這里就介紹一個非同一般的算法，以保證在最壞情況下也能達到線性時間。

這個SELECT算法的基本思想就是要保證對數組的劃分是一個好的劃分，它通過自己的方法選取主元（pivot），然后將pivot作為參數傳遞給快速排序的確定性劃分操作PARTITION。

基本步驟：

①.將輸入數組的n個元素劃分為n/5（上取整）組，每組5個元素，且至多只有一個組有剩下的n%5個元素組成。

②.尋找每個組織中中位數。首先對每組中的元素（至多為5個）進行插入排序，然后從排序后的序列中選擇出中位數。

③.對第2步中找出的n/5（上取整）個中位數，遞歸調用SELECT以找出其中位數x。（如果是偶數取下中位數）

④.調用PARTITION過程，按照中位數x對輸入數組進行劃分。確定中位數x的位置k。

⑤.如果i=k，則返回x。否則，如果i < k，則在地區間遞歸調用SELECT以找出第i小的元素，若干i > k，則在高區找第(i-k)個最小元素。

如下圖所示：

總結：

RANDOMIZED-SELECT和SELECT算法是基于比較的。我們知道，在比較模型中，排序時間不會優于Ω(nlgn)。之所以這里的選擇算法達到了線性時間，是因為它們沒有使用排序就解決了選擇問題。另外，我們沒有使用線性時間排序算法（計數排序/桶排序/基數排序），是因為它們要達到線性時間對輸入有很高的要求，而這里不需要關于輸入的任何假設。