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

一、問題描述：

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

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

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

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

二、期望線性時(shí)間的解決方案：

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

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

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

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

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); 
} 
 
/* 測(cè)試 */ 
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; 
} 

三、最壞情況線性時(shí)間的解決方案

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

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

基本步驟：

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

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

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

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

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

如下圖所示：

總結(jié)：

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

最新評(píng)論