|
在一个无序数组中，想得到Kth小的元素。首先大家想到的一定是先排序，然后再输出A[k]; 那么不使用排序，还有什么解决办法呢？
下面介绍一种算法，随机选择算法 Rand-Select(int A[], int p, int q, int i ),表示在数组A中[p, q]区间上寻找第i小的元素，这种算法会用到随机分割方法（在随机化快速排序算法中有介绍)。伪代码如下：
if(p=q) then return A[p];
r = RandPartition(A,p,q); //r 为划分元素的序号，即
A ————————————————————————————
| 《a[r] 【】 >a[r] |
————————————————————————————
p r q
[ k=r-p+1 ]
k = r-p+1
然后比较分割后得到的r与k之间的大小（因为k表示A[r]为第kth小元素）
if (i=k) then return A[r];
else if(i<k) then return Rand-Select(A, p, r-1, i)
else then return Rand-Select(A, r+1, q, i-k)
具体事例如下
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int Rand_Part(int a[], int p, int q);
/*
由函数Rand_Part, r为从p开始第kth个元素分别判断所求i与k大小
注意：
当i>k，由于已分割为右边，所以此时i = i-k;
*/
int Rand_Select(int a[],int p ,int q, int i){
if(p==q) return a[p];
else{
int r = Rand_Part(a,p,q);
int k = r-p+1;
if(i==k) return a[r];
else if(i<k) return Rand_Select(a,p,r-1,i);
else return Rand_Select(a,r+1,q,i-k);
}
}
//以后常用，所以单独提出来作为函数
void swap(int &a, int& b)
{
int temp = a;
a = b;
b = temp;
}
//分割—— key为主元
//尤其注意在循环时 i!=j
//最后交换主元与 a[i]; 分成两部分 左边为《key,右边为>KEY
//return 主元所在的位置
int Rand_Part(int a[], int p, int q)
{
int size = q-p+1;
int r = rand()%size + p;
swap(a[r],a[p]);
int i = p;
int key = a[p];
for (int j=i+1; j<=q;j++)
{
if(a[j]<key){
i++;
if(i!=j) //***Very Important easy to forget
swap(a[i],a[j]);
}
}
swap(a[p],a[i]);
return i;
}
int main()
{
// 2,3,5,6,8,10,11,13
int a[]={6,10,13,5,8,3,2,11};
int k = Rand_Select(a,0,7,6);
cout<<k<<endl;
}
最后分析该算法运行时间，前提假设为数组中各元素各不相同。【使用递归解决方法：主方法（Master Method）】
1.最优情况下，T(n) = T(9/10 *n)+θ(n) 或者 T(n) = T(1/2 *n)+θ(n) 常数分配下结果一样，为θ(n)；
2.最坏情况下， T(n) = T(n-1)+θ(n),代表每一次分割其他元素都大于或都小于主元，结果为θ(n^2)。
一般情况下，我们的运行时间复杂度为线性的。 | 
转播
