C++完成第K順序統計量的求解辦法。本站提示廣大學習愛好者：（C++完成第K順序統計量的求解辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是C++完成第K順序統計量的求解辦法正文
一個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)。之所以這裡的選擇算法到達了線性時間，是由於它們沒有運用排序就處理了選擇問題。另外，我們沒有運用線性時間排序算法（計數排序/桶排序/基數排序），是由於它們要到達線性時間對輸出有很高的要求，而這裡不需求關於輸出的任何假定。
