1.问题描述
对于一个非有序的数组A[p..r]，求数组中第k小的元素
2.如何考虑
排序就不用说了。。o(nlgn)，当然如果在实际情况中要一直取值，当然要排序后，一次搞定，以后都是O(1)
我们这里提供了取一次最K小的一个o(n)的解法， 用了快速排序的一种思想， 关键在于划分只一个部分，我们知道快速排序选择一个pivot对数组进行划分，左边小于pivot，右边大于等于pivot， 所以我们计算左边小于pivot(加上pivot)的个数count总共有多少，如果等于k,正是我们所要的，如果大于k，说明第k小的 数在左边，那就在左边进行我们的递归；否则，在右边，那么说明右边的第k-count小的数就是我们所要的，在右边进行 我们的递归。