考研ds 快排手写代码写法以及o(n)找第k大数方法
作者:
smile_922
,
2024-09-19 13:12:48
,
所有人可见
,
阅读 8
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int huafen(int A[],int L,int R){
int mid = A[L];
while(L<R){
while(A[R]>=mid&&L<R)R--;
A[L]=A[R];
while(A[L]<=mid&&L<R)L++;
A[R]=A[L];
}
A[L]=mid;
return L;
}
void quick_sort(int A[],int L,int R){
if(L>=R)return;
int mid = huafen(A,L,R);
quick_sort(A,L,mid);//写L->mid-1会mle,循环划分
quick_sort(A,mid+1,R);
}
int find(int A[],int n,int k){
int l=1,r=n;
while(l<r){
int mid = huafen(A,l,r);
if(mid>=k)r=mid;
else l=mid+1;
}
return A[l];
}
int main(){
int n,k;cin>>n>>k;
int A[100001]={0};
for(int i=1;i<=n;i++)cin>>A[i];
quick_sort(A,1,n);
cout<<A[k];
// cout<<find(A,n,k);
return 0;
}