快排例题——第k个数

做道简单一点的题巩固一下

基本思路

与上一个整体相似，通过快速排序将长度为n的整数数列变为从小到大的有序数组，在拿出其中第k个数。

题目描述
给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式
输入共两行。
第一行包含整数 n和k。
第二行包含 n 个整数（所有整数均在 1～1e9 范围内），表示整个数列。

输出格式
输出一个整数，表示数列的第 k 小数。

数据范围
1≤n≤100000
1≤k≤n

输入样例
5 3
3 1 2 4 5

输出样例
3

具体实现

1. 模板
实现思路：
我们假设小于分界点的个数为sl，大于分界点的个数为sr。

此时，整体便会分为两种情况：

当k≤sl时，第k小的数一定在分界点的左边，此时只需要对左边进行递归排序，第k小的数在sl上仍为第k个数。
当k≥sl时，第k小的数一定在分界点的右边，此时只需要对右边进行递归排序，第k小的数在sr上变为第 k-sl 个数。
代码注解：
在C++当中，如果局部变量和全局变量重名时，会优先使用局部变量，因此可以重名。

因为 1≤k≤n ，所以如果 l≥r 的话，就说明整个数列当中只有一个数，此时这个数便是我们的答案，因此返回 q[l]，q[r] 均可。

从 l 到 j 一共有 j-l+1 个数，此时让k与其进行比较，决定我们应该对哪部分区间进行递归处理（具体可见上面实现思路）。

实现代码
?

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int n,k;
int q[N]; 
int quick_sort(int q[],int l,int r,int k)
{
	if(l>=r)
	{
		return q[l];
	}
	int x=q[l+r>>1],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]);
		}
	}
	if(j-l+1>=k)
		{
		    return quick_sort(q,l,j,k);  
		}
		else
		{
		    return quick_sort(q,j+1,r,k-(j-l+1));
		}
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>q[i];
	}
	cout<<quick_sort(q,0,n-1,k)<<endl;
	system("pause");
	return 0;
}

2.?STL

代码注解：

STL大法好，这里只需注意我从 i=0 开始的，因此，第k个数对应在数组当中对应的应为第 k-1 个数。

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int n,k;
int q[N]; 
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>q[i];
	}
	sort(q,q+n);
	cout<<q[k-1]<<endl;
	system("pause");
	return 0;
}