這個問題的解決方法很多啊，一下列舉一下
1 基于排序的傳統方法 O(nlogn)
如果你只需要找一次第k小的數，這不是一個好方法。。。如果你要找n次，還是用排序吧
2 Las Vegas概率算法
也可以稱之為隨機化算法，其算法的特點優點類似于快速排序，都是需要選擇pivot，然后進行劃分。把一個序列劃分為3部分，x 小于x 和大于x的。。然后根據k的取值，進行遞歸計算。
畢竟是LasVegas算法，其最壞時間復雜度很差，是O(n^2)。。當然，平均復雜度非常好 O(n) 如果學過隨機化算法，證明不難！
3 基于r劃分的O(n)算法
這個算法可以說是一個trick，他的思想就是想優化LasVegas算法中的pivot選擇。。所以才會有這個算法。假設我們把r取成5的話，以每5個元素為子集劃分源數組，然后對每個子集排序求出中位數，這樣的中位數集合組成一個新的序列M，對M遞歸的求解其中位數p，得到的p即為劃分點。p將源數組劃分為3部分：
* s1：所有小于p的元素
* s2: 所有等于p的元素
* s3: 所有大于p的元素
下一輪迭代的時候根據輸入的level參數判斷該剪去哪部分元素。
這樣，每一輪迭代至少剪去n/4的元素（畫個中位數排列的圖出來就容易看出），則最壞情況下的時間復雜度表示為：
T(n)<=T(3n/4)+T(n/5)+O(n)
其中
* T(3n/4)是下一輪迭代的最大數據量情況下的時間復雜度
* T(n/5)是求尋找中位數組成集合的中位數的時間復雜度
利用歸納法，可以很清楚的證明出來T(n) <=20cn (c為常數)
基于r劃分的算法，其最壞時間復雜度是O(n)。。感覺是不是很優秀！但是，優秀的代價是你的常數因子太大了?。。?#160;
平時在選擇算法的時候，基本上可以說是一邊倒的選擇Las Vegas算法！
此外，在解決問題的時候，最好看清楚題目的情景，如果題目要求n個數中的第k個數，但是k取從1-n。。。那么還是用基于排序的吧。。。畢竟做了O(nlogn)的工作之后，每次都是O(1)搞定。。而LasVegas算法和基于r劃分的方法都要O(n^2)
基于LasVegas算法的代碼：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define Max 10000
int cnt=0;
int select( int *a, int b, int e, int k) //從b到e
{
cnt++;
if (b==e) return a[b];
int x=a[b+rand()%(e-b+1)],i=b,j=e;
i--;j++;
while (i<j)
{
while (a[++i] < x); while (a[--j] > x);
if (i<j)std::swap(a[i],a[j]);
}
if (j==e)j--;i=j-b+1;
if (k <=i) return select(a,b,j,k);
else return select(a,j+1,e,k-i);
}
int main()
{
int a[Max];
for(int i=0;i<Max;i++)
a[i]=i;
random_shuffle(a,a+Max);
int b[Max];
for(int i=0;i<Max;i++)
b[i]=a[i];
cout<<endl;
vector<int> C;
for(int i=0;i<Max;i++)
{
cnt=0;
select(a,0,Max-1,i);
for(int i=0;i<Max;i++)
a[i]=b[i];
C.push_back(cnt);
}
sort(C.begin(),C.end());
cout<<C[0]<<endl;
cout<<C[C.size()-1]<<endl;
return 0;
}
從代碼結果可以看出LasVegas算法表現還是很優秀的，畢竟10000個數，最深遞歸層次是35層！
此外，當然求第k小元素的各種復雜數據結構也可以做，而且效率也可以，看第四種方法： (這種方法等以后再總結吧。。)
回顧樹狀數組的定義，注意到有如下兩條性質：
一，c[ans]=sum of A[ans-lowbit(ans)+1 ... ans];
二，當ans=2^k時，
c[ans]=sum of A[1 ... ans];
下面說明findK(k)如何運作：
1，設置邊界條件ans,ans'<maxn且cnt<=k；
2，初始化cnt=c[ans]，其中ans=2^k且k為滿足邊界條件的最大整數；
3，找到滿足邊界條件的最大的ans'使得ans'-lowbit(ans')=ans，即ans'滿足c[ans']=A[ans+1 .. ans']（根據性質一），只要將c[ans']累加到cnt中（此時cnt=sum of A[1 ... ans']，根據性質二），cnt便可以作為k的逼近值；
4，重復第3步直到cnt已無法再逼近k，此時ans剛好比解小1，返回ans+1。
因此findk(k)的實質就是二分逼近
/**********************************
樹狀數組實現查找K小的元素
經典。
限制：數據范圍在1<<20 以內
***********************************/
#include <iostream>
using namespace std;
#define maxn 1<<20
int n,k;
int c[maxn];
int lowbit(int x){
return x&-x;
}
void insert(int x,int t){
while(x<maxn){
c[x]+=t;
x+=lowbit(x);
}
}
int find(int k){
int cnt=0,ans=0;
for(int i=20;i>=0;i--){
ans+=(1<<i);
if(ans>=maxn || cnt+c[ans]>=k)ans-=(1<<i);
else cnt+=c[ans];
}
return ans+1;
}
void input(){
memset(c,0,sizeof(c));
int t;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&t);
insert(t,1);
}
printf("%d\n",find(k));
}
int main(){
int cases;
scanf("%d",&cases);
while(cases--){
input();
}
return 0;
}