算法题

设A为一个有n个数的无序可重复数列
要取得这个数列里第k小的那个数
即把A排序后 脚标为k的那个元素
先提醒一下 排序本身的时间代价是不可能只用O(n)的
所以就需要想不排序就获得结果的算法

很久没有来了。。。大家还好吗

1、取决于特定的环境，排序可以在O(n)的情况下完成，比如，待排序的数是在某个可接受范围内的整数

2、普通情况，这个问题是经典的快速选择问题，分治算法的经典表现，步骤如下：
step1：从A中随机选择一个数P；
step2：从A中挑选出所有大于P的数；
step3：如果大于P的数的数量是k-1，那么p就是结果，算法结束；
step4：如果大于P的数的数量小于k-1，到step6；
step5：如果大于P的数的数量大于k-1，到step7；
step6：将小于P的数组成新的数组A'，并回到第一步，递归的对这个数组执行本算法，但是寻找的目标修改为n - k
step7：将大于P的数组成新的数组A'，并回到第一步，递归的对这个数组执行本算法

C++代码可以参考任何一个STL的算法nth_element

算法的平均时间复杂度是O(n)