用类快排的方法找寻 第n小 的数,找寻,Python语言: 用类
文章由Byrx.net分享于2019-03-23 09:03:47
用类快排的方法找寻 第n小 的数,找寻,Python语言: 用类
Python语言: 用类快排的方法找寻"第n小"的数#coding=utf-8## from: <a href="http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/269554">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#该片段来自于http://byrx.net
评论关闭