快速排序求第k小的数字

为什么要用快排求第k小的数字？
快排的特点，是先找参考值x，然后排序，最后递归。我们可以在递归的过程中，判断递归时候的子数组长度，看看与x的关系。
要知道，第k个小的数字无非就是从小到大排序后的第k个数字。
求第k大的数字及是求第n-k+1小的数字。
代码如下
注意递归条件和k的变化

#include<bits/stdc++.h>

using namespace std;

const int N = 8e6 + 6;

int t,n,k,q[N];

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) 
	{
		do i++; while(q[i]<x);
		do j--; 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()
{
	scanf("%d %d",&n,&k);
	for (int i = 0; i < n; i ++ ) scanf("%d",&q[i]);
	cout<<quick_sort(0,n-1,k)<<endl;
	return 0; 
 } 

纪录一个函数将第k个数放在正确位置上

nth_element(q,q+k-1,q+n);
cout<<q[k-1]<<endl; 

最后

以上就是成就咖啡为你收集整理的快速排序求第k小的数字的全部内容，希望文章能够帮你解决快速排序求第k小的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。