非递归的o（n）的求n个数里面第k大数的算法

Question

非递归是为了防止栈溢出，因为可能有10000000个数，不要平均时间复杂度为o（n）的算法，要最坏的时间复杂度也是o(n)的算法（所以基于快排思想的求第k大数的算法不要），坐等大牛解答~！
或者直接提供能够求n个数里面的中位数的算法也可~

Answer 1

如果ai范围小,如ai<=10000000,则使用桶排。
否则使用楼上的方法，加入二分思想O（n*logk）；
在求中位数时，其实也可以想出O（nlogn),并且O（nlogai）的算法是存在的。
如果是长整型，则O<=310000000,很不错。

Answer 2

k如果小的话，另开一个数组sortarray,只保留k个数。
把原来数组里的数一个个加入sortarray,将k+1大的数舍去。
复杂度为k*o(n);追问

这个方法不错。但对于求中位数，复杂度就为O(n^2)了，这个时候有没有更高效的算法？