原题在这里
题目大意：给定n个数，求出这n个数中第k小的数。
做法：
- 首先直接想到的肯定是直接排序然后O(1)输出即可。这样的时间复杂度是O(nlogn)，由于题目中n的数据范围过大我们无法接受。
- 再想到，我们在进行快速排序的过程中，随机选取一个数作为基准，每次将比它大的数放到它的左边，比它小的数放到它的右边，那么我们是不是可以考虑：当任选取一个基准并进行以上操作之后，如果我们要求的第k小的数在这个基准的左边，那我们只需要递归左边就可以了，右边的数对得出答案是没有贡献的。反之如果在右边，那么只需要递归右边即可。这样就避免了大量的无效操作，时间复杂度也来到了O(n)。
void quicksort(int l,int r) {
int mid = a[(l + r) >> 1];
int ll = l,lr = r;
do {
while(a[ll] < mid) ll++;
while(a[lr] > mid) lr--;
if(ll <= lr) {
swap(a[ll],a[lr]);
ll++;
lr--;
}
}while(ll <= lr);
if(k >= ll) quicksort(ll,r);
else if(k <= lr) quicksort(l,lr);
else {
cout << a[k];
return;
}
}
注意我们在进行一次do-while操作之后ll应该是大于lr的，也就是整个区间被分为了ll <= lr < ll <= r这三部分，也就导致了后面的if语句中为什么是k >= ll, k <= lr和ll < k < lr这三种情况。
3. STL当中给我们提供了一个非常方便的函数nth_element(a+x,a+x+y,a+x+n)，作用是使a数组中下标x到x+y-1的元素都小于a[x+y]，而x+y+1到x+n的元素都大于a[x+y]，这样此题就会变得非常简单。