选择问题是我看数据结构与算法分析C中的第一个问题，问题是在一个未排序的数组中，找出第K大的数。对这个问题最直观的解法是排序后输出相应的数，但是在超大数据下，该算法时间复杂度取决于排序的算法，最快也是不能超过O(NlogN)的，因为排序最快就是O(NlogN)，对此如何再次基础上优化呢？
如果需求的是最小的数，那么直接循环依次，就能找出最小的，也就是说选择问题的需要的时间是一定小于排序整个数组的，以快排为例的话，在选择了中间数左右已经分开后，如果中间的下标就是相应的需求的下标的话，就可以得出答案。
<pre>
encoding=utf8
def max_k(a):
k = len(a)//2
for index in range(k):
for rest in range(index+1, len(a)):
if a[index] < a[rest]:
a[index], a[rest] = a[rest], a[index]
return a[k-1]
def max_k2(a, k):
if len(a) == 0:
return "shuruweikong"
result, index = paixu(a)
if index == k:
return result[k]
elif k < index:
return max_k2(result[0:index], k)
elif k > index:
return max_k2(result[index+1:], k-index-1)
def paixu(a):
p = a[0]
left = []
right = []
for item in a[1:]:
if item <= p:
left.append(item)
elif item > p:
right.append(item)
index = len(left)
return left+[p]+right, index
def main():
test = [5, 25, 7, 2, 4, 8, 34, 76, 23]
test2 = [5, 4, 7, 2, 3, 8]
k = len(test)//2
new_k = len(test) - k
print(max_k2(test, new_k))
if name == 'main':
main()
</pre>
以上是Py的代码，写的比较野，也不知道有没有BUG，仅供参考！
文章内容如有错误，请在评论区指出。
