顺序统计量（Order statistic）

一个n位元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。例如，最小值是第一个顺序统计量（i=1），最大值是第n个顺序统计量(i=n)。

中位数（Median）

中位数是顺序统计量的一种，它是集合中的中点元素，与上述顺序统计量的描述一致，i从1开始计数。当n为奇数时，中位数有唯一一个，位于i=(n+1)/2处，当n为偶数时，中位数有两个，分别为上中位数(n/2)与下中位数(n/2+1)。

问题与定义

讨论中一个由n个互异的元素构成集合中选择第i个顺序统计量的问题，为方便讨论，假设元素都是互异的，但实际上这里的讨论都可以推广到包含重复元素的集合中。对这一问题的形式化定义为

  • 输入：一个包含n个互异元素的集合A和一个整数i，1≤ i ≤n。
  • 输出：元素x属于集合A，且A中恰好有i-1个其它元素小于它。

基本思想

随机划分

使用类似快排的划分思路，选择一个主元（pivot），将序列中的其它元素进行划分为小于等于主元和大于等于主元的两个子序列，如果主元的顺序统计量就是要查找的顺序统计量则查找成功，如果目标顺序统计量小于主元的顺序统计量，则从较小的子序列中根据上述同样的过程进行查找，否则则在较大的子序列中进行查找。

确定性划分

确定性划分首先将序列分为较小的组，每一组有一个较小常数数量的元素，对每个分组进行排序，找出每组的中位数，然后对每组的中位数用同样的方式进行划分后查找这些中位数的中位数。利用每组中位数的中位数作为主元对序列进行划分，划分后的处理方式与随机划分相似。这里的重点是分组后的中位数的中位数x可以将序列划分为较为平均的两部分，因为，各分组的中位数y小于x的分组中小于中位数y的必定也小于x，中位数y大于x的分组中大于y的元素也必定大于x，它们大约各占整个序列的1/4，这样就避免了随机划分可能出现较差的情况。

实现

使用随机划分子序列的算法

def swap(A, i, j):
    temp = A[i]
    A[i] = A[j]
    A[j] = temp

def random_select(A, p, r, i):
    """
    A: 要查找的序列
    p: 序列开始索引，包含
    r: 序列结束索引，包含
    i: 要查找的顺序统计量
    """
    # 如果只有一个元素，直接返回
    if p == r:
        return A[p]
    q = random_partition(A, p, r)
    if i == q:
        return A[q]
    if i < q:
        return random_select(A, p, q-1, i)
    else:
        return random_select(A, q+1, r, i)
    
def random_partition(A, p, r):
    """
    A: 要划分的序列
    p: 序列开始索引，包含
    r: 序列结束索引，不包含
    """
    # 这里直接从中间进行划分
    mid = (p + r) / 2
    pivot = A[mid]  # 主元
    left = p        # [p,left)间的元素都小于等于主元
    right = r       # (right,r]间的元素都大于等于主元
    while left < right:
        if A[left] >= pivot and A[right] <= pivot: 
            swap(A, left, right)
            left += 1
            right -= 1
        else:
            if A[left] < pivot:
                left += 1
            if A[right] > pivot:
                right -= 1
    return left
        

def main():
    A = [100, 134, -1, 1324, 1123, 9, 34, 3, -98, 132, 3, 3, 12, 29, 36]
    for i in xrange(0, len(A)-1):
        print random_select(A, 0, len(A)-1, i)

if __name__ == '__main__':
    main()

使用确定性划分的算法

def swap(A, i, j):
    temp = A[i]
    A[i] = A[j]
    A[j] = temp

def insertion_sort(A, r):
    for i in xrange(0, len(r)):
        current = i
        for j in xrange(i, -1, -1):
            if A[r[current]] < A[r[j]]:
               swap(A, r[current], r[j])
               current = j

def median(A, r):
    # print "median", r
    insertion_sort(A, r)
    if len(r) % 2 == 1:
        return r[len(r) / 2]
    else:
        return r[len(r) / 2 - 1]

def select(A, r, i):
    # print "select", r
    """
    A: 要查找顺序统计量的序列
    r: 查找的序号
    """
    size = len(r)
    if size == 1:
        return r[0]
    start = r[0]      # start index in A
    end = r[size - 1] # end index in A
    medians = []
    if size % 5 == 0:
        num = size / 5
    else:
        num = size / 5 + 1
    for j in xrange(0, num):
        s = j * 5    # start index of r
        e = s + 5    # end index of r
        if e >= size:
            e = size
        m = median(A, r[s : e])
        medians.append(m)
    x = select(A, medians, i)
    k = partition(A, x, start, end)
    # print "after partition", i, k, x, start, end
    if i == k:
        return x
    elif i < k and k > start:
        return select(A, range(start, k), i)
    else:
        return select(A, range(k+1, end+1), i)

def partition(A, x, p, r):
    # print "partition", x, p, r
    pivot = A[x]
    left = p        # [p,left)间的元素都小于等于主元
    right = r       # (right,r]间的元素都大于等于主元
    while left < right:
        if A[left] >= pivot and A[right] <= pivot: 
            swap(A, left, right)
            left += 1
            right -= 1
        else:
            if A[left] < pivot:
                left += 1
            if A[right] > pivot:
                right -= 1
    return left


def main():
    A = [100, 134, -1, 1324, 1123, 9, 34, 3, -98, 132, 3, 3, 12, 29, 36]
    for i in xrange(0, len(A)):
        print A[select(A, range(0, len(A)), i)]

if __name__ == '__main__':
    main()