用类快排的方法找寻"第n小"的数，方法找寻,[Python]代码Py

用类快排的方法找寻"第n小"的数，方法找寻,[Python]代码Py

[Python]代码

Python语言: 用类快排的方法找寻"第n小"的数#coding=utf-8## from: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/269554# 代码描述：#  O(n) quicksort style algorithm for looking up data based on rank order.#  Useful for finding medians, percentiles, quartiles, and deciles.#  Equivalent to data[n] when the data is already sorted.import randomdef select(data, n):    "Find the nth rank ordered element (the least value has rank 0)."    data = list(data)    if not 0 <= n < len(data):        raise ValueError('not enough elements for the given rank')    while True:        pivot = random.choice(data)        pcount = 0        under, over = [], []        uappend, oappend = under.append, over.append        for elem in data:            if elem < pivot:                uappend(elem)            elif elem > pivot:                oappend(elem)            else:                pcount += 1        if n < len(under):            data = under        elif n < len(under) + pcount:            return pivot        else:            data = over            n -= len(under) + pcount