第k小整数(快排)

题目描述

“哇，好多冰淇淋啊！”张琪曼跑到学院的冷饮店，伸出2根手指对冰淇淋老板说，“来3个。”老板蒙了，问：“几个？”张琪曼又伸出3根手指说“2个。”
老板满头大汗：“我不管你要几个，只要你能从你的口袋里的魔法石里找出第k小的魔法石，冰淇淋随便你吃。”
现在你知道该怎么做了吧？那就是：对于给定的n个元素的无序数组，要求从中找出第k小的元素。

输入

第一行是总数n（1<n<100000）和k，第二行是n个待比较元素。

输出

第k小的数在数组中的位置。

样例输入

5 3
25 9 90 57 3

样例输出

1

快速排序（时间复杂度小于2n）

区间[L,R]

1.找到分界点x(三种选择q[L],q[R],q[(L+R)/2])

2.左边所有数Leftx

   右边所有数Rightx

3.递归排序Left，递归排序Right

①(为左区间长度)，递归Left

②，递归Right（k-）

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,q[100005],pos[100005];
int quick_sort(int l,int r,int k){if(l==r)return q[l];int x=q[l],i=l-1,j=r+1;while(i<j){while(q[++i]<x);while(q[--j]>x);if(i<j)swap(q[i],q[j]);}int sl=j-l+1;if(k<=sl)return quick_sort(l,j,k);return quick_sort(j+1,r,k-sl);
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=0;i<n;i++){cin>>q[i];if(pos[q[i]]==0)pos[q[i]]=i+1;}int d=quick_sort(0,n-1,k);cout<<pos[d];return 0;
}