做道简单一点的题巩固一下
基本思路
与上一个整体相似，通过快速排序将长度为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; }
