快速选择法（时间复杂度O（2n））

快速选择法（时间复杂度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 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5702981.html