algo - 中位数 (medians select)

sigsegv11

中位数选择：找出一个序列的排名（排序）第nth个数字，类似于quicksort的算法，但较quicksort更为简单，算法平均复杂度O(n)，小于quicksort的平均复杂度O(n*lg(n))。
Divide & Conquer的典型
parititon函数同quicksort的完全一样:
partition.py:
from random import randrange
"""
quick sort randomized parition (pivot)
"""
def partition(A, p, r):
    def _xchg(_A, _l, _r):
        t = _A[_l]
        _A[_l] = _A[_r]
        _A[_r] = t
    def _partition(_A, _p, _r):
        x = _A[_r - 1]
        i = _p
        for j in range(_p, _r - 1):
            if _A[j]  x:
                _xchg(_A, i, j)
                i += 1
        _xchg(_A, i, _r - 1)
        return i
    pivot = randrange(p, r)
    _xchg(A, pivot, r - 1)
    return _partition(A, p, r)
算法median select (median_select.py):
from partition import partition
from quicksort import quicksort
def median_select(L, n):
    def _midselect(A, p, r, i):
        if p == r:
            return A[p]
        q = partition(A, p, r)
        k = q - p + 1
        if i == k:
            return A[q]
        elif i  k:
            return _midselect(A, p, q, i)
        else:
            return _midselect(A, q + 1, r, i - k)
    return _midselect(L, 0, len(L), n)
if __name__ == '__main__':
    import sys
    import random
    ln = len(sys.argv)
    num = 100
    nth = 0
    if ln == 2:
        nth = int(sys.argv[1])
    elif ln == 3:
        nth = int(sys.argv[1])
        num = int(sys.argv[2])
    L = [random.randrange(num, 10 * num) for x in range(0, num)]
    print L
    print median_select(L, nth)
    quicksort(L)
    print L
quicksort.py为已经给出的quicksort的算法，不过将partition函数拆分了出来：
quicksort.py:
from partition import partition
def quicksort(L):
    ln = len(L)
    def _quicksort(A, p, r):
        if p  r:
            q = partition(A, p, r)
            _quicksort(A, p, q)
            _quicksort(A, q + 1, r)
    _quicksort(L, 0, ln)
if __name__ == '__main__':
    import sys
    import random
    num = 100
    if len(sys.argv) == 2:
        num = int(sys.argv[1])
    L = [ random.randrange(10, 1000) for x in range(num) ]
    print L
    quicksort(L)
    print L


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/98727/showart_2111993.html