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

一、問題描述：

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

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

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

一種原始的解決方案是，用堆排序或歸并排序?qū)⑤斎霐?shù)據(jù)進行排序，然后返回第k個元素。這樣在Θ(nlgn)時間內(nèi)一定可以解決。但是我們希望有更好的方案，最好是線性時間。

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

為了在線性時間內(nèi)解決這個選擇問題，我們使用一個隨機的分治算法，即RANDOMIZED-SELECT算法。此算法是使用隨機化的快速排序中的隨機劃分子程序，對輸入數(shù)組進行隨機劃分操作，然后判斷第k小元素在劃分后的哪個區(qū)域，對所在區(qū)域進行遞歸劃分，最后找到第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()是隨機版的劃分操作（快速排序的分析與優(yōu)化），可見本算法是一個隨機算法，它的期望時間是Θ(n)（假設(shè)元素的值是不同的）。

1、Lucky-Case：最好的情況是在正中劃分，劃分的右邊和右邊的元素數(shù)量相等，但是1/10和9/10的劃分也幾乎一樣好?？梢赃@么說，任何常數(shù)比例的劃分都和1/2:1/2的劃分一樣好。這里以1/10和9/10的劃分為例，算法運行時間遞歸式為T(n) <= T(9n/10) + Θ(n)，根據(jù)主定理得到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)出現(xiàn)的概率非常非常小，但是不代表它不會出現(xiàn)。這里就介紹一個非同一般的算法，以保證在最壞情況下也能達到線性時間。

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

基本步驟：

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

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

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

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

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

如下圖所示：

總結(jié)：

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

最新評論