快速选择法(时间复杂度O(2n))

快速选择法(时间复杂度O(2n)),第1张

快速选择法(时间复杂度O(2n))

简单说一下思路

快速选择法在快速排序法上进行深化,其实质还是二分思想

首先没看过快速排序法,先去看快排,这里不啰嗦了

这里要确定第k个数在哪一个区间,这决定了递归的方向

k属于[ L , mid ]对左边进行递归

k属于( mid, R]对右边进行递归

不断进行递归直到 i=j 为止

此时,第i(j)个数就是第k个数

题目如下:

题目如下:先输入n(n<=100000),k(k<=n);然后输入n个数。对n个数进行升序排序,然后输出第k个数。

输入如下:

10 5
54 87 51 25 59 17 97 12 28 15

输出如下:

28

 code:

#include
using namespace std;
int n,k;
const int N=1e6+10;
int q[N];

int isort(int l,int r,int k){
   if(l==r) return q[l];
   int mid=q[l],i=l-1,j=r+1;
   while(imid);
       if(i 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5702981.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存