# -*- coding: utf-8 -*-
from random import randint
from math import ceil, floor
def _partition(A, l, r, i):
"""以A[i]为主元划分数组A[l..r],使得:
A[l..m-1] <= A[m] < A[m+1..r]
"""
A[i], A[r] = A[r], A[i] # i交换到末位r,作为主元
pivot = A[r] # 主元
m = l # 索引标记
for n in xrange(l, r): # l..r-1
if A[n] <= pivot:
A[m], A[n] = A[n], A[m] # 交换
m += 1 # 后移
A[m], A[r] = A[r], A[m] # 主元到m位
return m
def _rand(A, l, r):
"""随机划分主元"""
return randint(l, r) # A[l..r]随机取一个
def _select(A, l, r, k, pivot_selector = _rand):
"""利用快排,得A[l..r]中第k小的数,k in [l+1,r+1]:
其尾递归方式,伪码如下:
SELECT(A, l, r, k)
1 while true:
2 i ← ? // 划分主元位置
3 m ← PARTITION(A, l, r, i) // 数组划分
4 n ← m - l + 1 // A[l..m]元素个数
5 if k = n // 检查A[m]是否是第k小的元素
6 then return A[m]
7 elseif k < n // 左划分区
8 r = m - 1
9 else // 右划分区
10 k = k - n
11 l = m + 1
Args:
pivot_selector(Function): 主元选取方法,默认随机方式
"""
if not A:
return None
if l == r:
return A[l]
while True:
i = pivot_selector(A, l, r)
m = _partition(A, l, r, i)
n = m - l + 1
if k == n:
return A[m]
elif k < n:
r = m - 1
else:
k = k - n
l = m + 1
def rand_select(A, k):
"""默认随机划分主元方式,k in [1, len(A)]
E[T(n)] = O(n)
"""
return _select(A, 0, len(A) - 1, k);
def _median(A, l, r):
"""对A[l..r]插入排序(原地)后选取其中位数位置"""
for j in xrange(l, r + 1):
k = A[j]
i = j
while i > l and A[i-1] > k:
A[i] = A[i-1]
i -= 1
A[i] = k
return l + int((r - l) * 0.5) # 下中位数
def _medianOfMedians(A, l, r):
"""中位数的中位数方式:
1. 划分为floor(n/5)个5元组,剩下(n%5)组成最后一组。
2. 找出ceil(n/5)个组各自的中位数。先对每组插入排序,再从中选出中位数。
3. 对第2步中找出的ceil(n/5)个中位数重复上述操作,直到仅有一个中位数。
"""
if l == r:
return l
n = r - l + 1 # 元素个数
m = int(ceil(n / 5.0)) # 划分组数,每组5个元素
for i in xrange(m):
# 每组起始位和结束位
sub_l = l + i * 5
sub_r = sub_l + 4
if sub_r > r:
sub_r = r
# 对每组元素插入排序后,选取中位数
sub_m = _median(A, sub_l, sub_r) # 中位数索引
# 交换中位数到前几位
j = l + i
A[j], A[sub_m] = A[sub_m], A[j]
return _medianOfMedians(A, l, l + m - 1) # 中位数的中位数
def bfprt_select(A, k):
"""中位数的中位数方式(BFPRT算法)
T(n) = O(n)
"""
return _select(A, 0, len(A) - 1, k, _medianOfMedians);
def _median3(A, l, r):
"""三数中位数方式,取l,r,(l+r)/2三数中位数"""
c = (l + r) / 2
keys = [l, c, r]
i = _median(keys, 0, 2)
return keys[i]
def median_select(A, k):
"""三数中位数方式,以消除最坏情况"""
return _select(A, 0, len(A) - 1, k, _median3);
if __name__ == '__main__':
import random, time
from copy import copy
print('preparing data...')
n = 1000000
nums = range(n)
random.shuffle(nums)
print('ready go!')
def timeit(fnc, *args, **kargs):
print('%s starts processing' % fnc.__name__)
begtime = time.clock()
retval = fnc(*args, **kargs)
endtime = time.clock()
print('%s takes time : %f' % (fnc.__name__, endtime - begtime))
return retval
test_methods = [rand_select, bfprt_select, median_select]
k = random.randrange(n) + 1
dashes = '---' * 10
for test in test_methods:
print(dashes)
nums_new = copy(nums)
result = timeit(test, nums_new, k)
print('the %dth smallest element: %d' % (k, result))
相关文章推荐
• Python NumPy教程之数据类型对象• Python标准库中的logging用法示例• python自动化测试实例解析• 详解Python中的条件判断语句• 在Django的视图(View)外使用Session的方法独孤九贱(3)_JavaScript视频教程
javascript是运行在浏览器上的脚本语言,连续多年,被评为全球最受欢迎的编程语言。是前端开发必备三大法器中,最具杀伤力。如果前端开发是降龙十八掌,好么javascript就是第18掌:亢龙有悔。没有它,你的前端生涯是不完整的。《php.cn独孤九贱(3)-JavaScript视频教程》课程特色:php中文网原创幽默段子系列课程,以恶搞,段子为主题风格的php视频教程!轻松的教学风格,简短的教学模式,让同学们在不知不觉中,学会了javascript知识。
JavaScript教程139843次播放
独孤九贱(6)_jQuery视频教程
jQuery是一个快速、简洁的JavaScript框架。设计的宗旨是“write Less,Do More”,即倡导写更少的代码,做更多的事情。它封装JavaScript常用的功能代码,提供一种简便的JavaScript设计模式,优化HTML文档操作、事件处理、动画设计和Ajax交互。 核心特性可以总结为:具有独特的链式语法和短小清晰的多功能接口;具有高效灵活的css选择器,并且可对CSS选择器进行扩展;拥有便捷的插件扩展机制和丰富的插件。兼容各种主流浏览器,如IE 6.0+、FF 1.5+、Safari 2.0+、Opera 9.0+等,是全球最流行的前端开发框架之一。PHP中文网根据最新版本,独家录制jQuery最新视频教程,回馈PHP中文网的新老用户。
jQuery教程114914次播放
jQuery与Ajax基础与实战
jQuery是最流行的JS函数库,封装了许多实用的功能,其中最引人入胜的就是Ajax。 jQuery中的Ajax操作,语法简单,操作方便,使Ajax从未如此轻松,前端人员从此不再为与服务器异步交互而发愁,本套课程,精选了最常用的几个方法,从基本的语法到每个参数,再到具体实例进行了全面的讲解。
AJAX教程14584次播放
Git教程(60分钟全程无废话版)
Git 是一个开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目。 Git 是 Linus Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。 Git 与常用的版本控制工具 CVS, Subversion 等不同,它采用了分布式版本库的方式,不必服务器端软件支持
JavaScript教程12589次播放