#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 random
def 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
#
# 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 random
def 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