第k小元素(顺序统计量)
在一个含有n个元素的集合中,有时我们需要找到第该集合中第kk个小的元素,这也被称作第kk个顺序统计量(order statistic)。在前面我们已学过排序, 我们可以将集合进行排序后,直接输出第kk个元素。但是我们目前我们知道的排序中最好的时间复杂度就是O(nlog(n))O(nlog(n)). 接下来我们要使用两种方法找出第k小元素,其在某些过程用到排序,但我们并不会对整个集合进行排序,也不会使