计算中值和选择问题.docx

选择问题是求一个n个数列表的第k个最小元素的问题。这个数字称为第k个顺序统计量。这个问题的另一个情况是在k=时，它要求找出这样一个元素，该元素比列表中的一半元素大，又比另一半元素小。这个中间的值被称为中值。 显然，为了找出第k个最小的元素，我们可以先把列表排序，然后从排序算法的输出中选出第k个元素。这样一种算法的运行时间取决于所选用的排序算法的效率。因此，如果使用类似合并排序这样优秀的排序算法，该算法的效率应该属于O(n log n)。但是，对于选择问题，利用排序有点杀鸡用牛刀。 划分 一般对于选择问题，可以采取划分的思路，将一个给定列表根据某个值p（例如列表中的第一个元素）进行划分。一般来说