C++完成第K次序統計量的求解辦法。本站提示廣大學習愛好者：（C++完成第K次序統計量的求解辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是C++完成第K次序統計量的求解辦法正文
一個n個元素構成的聚集中，第K個次序統計量（Order Statistic）指的是該聚集中第K小的元素，我們這裡要評論辯論的是若何在線性時光（linear time）裡找出一個數組的第K個次序統計量。該成績的算法關於C++法式員來講有必定的自創價值。詳細以下：
1、成績描寫：
成績：給定一個含有n個元素的無序數組，找出第k小的元素。
k = 1 ：最小值
k = n ：最年夜值
k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ ：中位數
找最年夜值或最小值很簡略，只須要遍歷一次數組並記載下最年夜值或最小值便可以了。我們在這裡要處理的成績是普通性的選擇成績。
一種原始的處理計劃是，用堆排序或合並排序將輸出數據停止排序，然後前往第k個元素。如許在Θ(nlgn)時光內必定可以處理。然則我們願望有更好的計劃，最好是線性時光。
2、希冀線性時光的處理計劃：
為了在線性時光內處理這個選擇成績，我們應用一個隨機的分治算法，即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;
}
3、最壞情形線性時光的處理計劃
固然最壞情形Θ(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)。之所以這裡的選擇算法到達了線性時光，是由於它們沒有應用排序就處理了選擇成績。別的，我們沒有應用線性時光排序算法（計數排序/桶排序/基數排序），是由於它們要到達線性時光對輸出有很高的請求，而這裡不須要關於輸出的任何假定。
