中位数和顺序统计量

在一个由个元素组成的集合中，第个顺序统计量是该集合中第小的元素。例如，在一个集合中，最小值是第个顺序统计量，最大值是第个顺序统计量。用非形式化的描述来说，中位数是它所属集合的“中点元素”。

将求解顺序统计量的问题定义为如下选择问题：
输入：一个包含个数的集合A和一个整数，。
输出：元素，且A中恰好有个其他元素小于它。

我们可以在的时间内解决这个问题，因为我们可以采用归并排序、堆排序或者随机化快速排序对输入数据进行排序，然后对排序好的集合输出第个元素即可。

这里将采用更好时间复杂度的方法解决这一问题。

我们借鉴随机化快速排序的方法，采用分治策略在集合中查找第个顺序统计量

• Devide
  和随机化快速排序相同，先将随机化主元放到正确的位置，如果该主元下标，则输出主元结束程序运行。
• Conquer
  如果，则对主元的左侧子序列递归搜索；如果，则对主元的左侧子序列递归搜索。
  最终将输出集合的第个顺序统计量
• Combine
  同随机化快速排序，这里不需要合并。

算法的Python3实现如下

import random

def partition(a, p, q):
    i = p
    for j in range(p+1, q):
        if a[j] < a[p]:
            i += 1
            a[i], a[j] = a[j], a[i]

    a[i], a[p] = a[p], a[i]
    return i

def randomized_select(a, p, q, i):
    if p > q:
        return
    r = partition(a, p, q)
    k = r - p + 1
    if i == k:
        return a[r]
    elif i < k:
        return randomized_select(a, p, r, i)
    elif i > k:
        return randomized_select(a, r+1, q, i-k)

if __name__ == '__main__':
    a = [4, 2, 3, 0, 1, 3, 2, 6]
    val = randomized_select(a, 0, len(a), 2)
    print(val)