代码
比这篇新的文章:
linux/init/main.c
比这篇旧的文章: 筛法生成质数（素数）的生成器
作者: 半瓶墨水, 点击436次, 评论(0), 收藏者(0)
打分:
所有评论，共0条：( 我也来说两句)
比这篇旧的文章: 筛法生成质数（素数）的生成器
用类快排的方法找寻"第n小"的数
语言: Python, 标签: 无 2008/06/30发布 6个月前更新作者: 半瓶墨水, 点击436次, 评论(0), 收藏者(0)
Python语言: 用类快排的方法找寻"第n小"的数
01 #coding=utf-8
02 #
03 # from: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/269554
04 # 代码描述：
05 # O(n) quicksort style algorithm for looking up data based on rank order.
06 # Useful for finding medians, percentiles, quartiles, and deciles.
07 # Equivalent to data[n] when the data is already sorted.
08
09 import random
10
11 def select(data, n):
12 "Find the nth rank ordered element (the least value has rank 0)."
13 data = list(data)
14 if not 0 <= n < len(data):
15 raise ValueError('not enough elements for the given rank')
16 while True:
17 pivot = random.choice(data)
18 pcount = 0
19 under, over = [], []
20 uappend, oappend = under.append, over.append
21 for elem in data:
22 if elem < pivot:
23 uappend(elem)
24 elif elem > pivot:
25 oappend(elem)
26 else:
27 pcount += 1
28 if n < len(under):
29 data = under
30 elif n < len(under) + pcount:
31 return pivot
32 else:
33 data = over
34 n -= len(under) + pcount
02 #
03 # from: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/269554
04 # 代码描述：
05 # O(n) quicksort style algorithm for looking up data based on rank order.
06 # Useful for finding medians, percentiles, quartiles, and deciles.
07 # Equivalent to data[n] when the data is already sorted.
08
09 import random
10
11 def select(data, n):
12 "Find the nth rank ordered element (the least value has rank 0)."
13 data = list(data)
14 if not 0 <= n < len(data):
15 raise ValueError('not enough elements for the given rank')
16 while True:
17 pivot = random.choice(data)
18 pcount = 0
19 under, over = [], []
20 uappend, oappend = under.append, over.append
21 for elem in data:
22 if elem < pivot:
23 uappend(elem)
24 elif elem > pivot:
25 oappend(elem)
26 else:
27 pcount += 1
28 if n < len(under):
29 data = under
30 elif n < len(under) + pcount:
31 return pivot
32 else:
33 data = over
34 n -= len(under) + pcount
所有评论，共0条：( 我也来说两句)