题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。
输入格式
第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。

输出格式
输出一个整数，表示数列的第k小数。

数据范围
1≤n≤100000,
1≤k≤n

样例

输入样例：
5 3
2 4 1 5 3
输出样例：
3

算法1

(归并排序) $O(nlogn)$

C++ 代码

//quick_sort

include[HTML_REMOVED]

using namespace std;
const int N = 1000010;
int p[N];

void quick_sort(int p[],int l ,int r){
if (l==r){return;}
int i=l-1,j=r+1,x=p[l];
while(i<j){
do i;while(p[i]<x);
do j;while(p[j]<x);
if(i<j){
swap(p[i],p[j]);
}else{
break;
}
}

quick_sort(p,l,j);
quick_sort(p,j+1,r);

}

int main(){
int n;
cin>>n;
for(int i=0;i[HTML_REMOVED]>p[i];
}
quick_sort(p,0,n-1);

for(int i=0;i<n;i++){
    cout<<p[i];
}
return 0;

}

merge_Sort

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N = 1e6+10;
int p[N];
int tmp[N];

void Merge_sort(int p[],int l,int r){
if(l==r) return;
int mid = l+r>>1;
Merge_sort(p,l,mid);
Merge_sort(p,mid+1,r);
int i=l,j = mid +1,k=0;
while(i<=mid&&j<=r){
if(p[i]<p[j]){
tmp[k]=p[i];
}else{
tmp[k]=p[j];
}
}
while(i<=mid) tmp[k]=p[i];
while(j<=r) tmp[k]=p[j];

for(int j=0,i=l;i<=r;i++){
    p[i] = tmp[j];
}

}

int main(){
int n;
cin>>n;
for(int i=0;i[HTML_REMOVED]>p[i];
}
Merge_sort(p,0,n-1);
for(int i=0;i<n;i++){
cout<<p[i]<<endl;
}
return 0;
}

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N=1e5+12;
int p[N];
int tmp[N];
void Merge(int p[],int l,int r){
if(l>=r) return ;
int mid = l+r>>1;
Merge(p,l,mid);
Merge(p,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(p[i]<=p[j]){
tmp[k] = p[i];
}else{
tmp[k] = p[j];
}
}

while(i<=mid)  tmp[k++] = p[i++];
while(j<=r)  tmp[k++] = p[j++];

for(int i=l,j=0;i<=r;i++,j++)p[i] = tmp[j];

}

int main(){
int n,k;
cin>>n;cin>>k;
for(int i=0;i[HTML_REMOVED]>p[i];
}
QSort(p,0,n-1);
cout<<p[k-1];
return 0;
}

算法2

(快速排序) $O(nlogn)$

C++ 代码

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N=1e5+12;
int p[N];
void QSort(int p[],int l,int r){
if(l>=r)return ;
int i=l-1,j=r+1,x=p[l];
while(i[HTML_REMOVED]x);
if(i<j){
swap(p[i],p[j]);
}
}
QSort(p,l,j);
QSort(p,j+1,r);
}

int main(){
int n,k;
cin>>n;cin>>k;
for(int i=0;i[HTML_REMOVED]>p[i];
}
QSort(p,0,n-1);
cout<<p[k-1];
return 0;
}