中位数选择：找出一个序列的排名（排序）第nth个数字，类似于quicksort的算法，但较quicksort更为简单，算法平均复杂度O(n)，小于quicksort的平均复杂度O(n*lg(n))。
Divide & Conquer的典型
parititon函数同quicksort的完全一样:
partition.py:
from random import randrange
"""
quick sort randomized parition (pivot)
"""
def partition(A, p, r):
def _xchg(_A, _l, _r):
t = _A[_l]
_A[_l] = _A[_r]
_A[_r] = t
def _partition(_A, _p, _r):
x = _A[_r - 1]
i = _p
for j in range(_p, _r - 1):
if _A[j] < x:
_xchg(_A, i, j)
i += 1
_xchg(_A, i, _r - 1)
return i
pivot = randrange(p, r)
_xchg(A, pivot, r - 1)
return _partition(A, p, r)
|
算法median select (median_select.py):
from partition import partition
from quicksort import quicksort
def median_select(L, n):
def _midselect(A, p, r, i):
if p == r:
return A[p]
q = partition(A, p, r)
k = q - p + 1
if i == k:
return A[q]
elif i < k:
return _midselect(A, p, q, i)
else:
return _midselect(A, q + 1, r, i - k)
return _midselect(L, 0, len(L), n)
if __name__ == '__main__':
import sys
import random
ln = len(sys.argv)
num = 100
nth = 0
if ln == 2:
nth = int(sys.argv[1])
elif ln == 3:
nth = int(sys.argv[1])
num = int(sys.argv[2])
L = [random.randrange(num, 10 * num) for x in range(0, num)]
print L
print median_select(L, nth)
quicksort(L)
print L
|
quicksort.py为已经给出的quicksort的算法，不过将partition函数拆分了出来：
quicksort.py:
from partition import partition
def quicksort(L):
ln = len(L)
def _quicksort(A, p, r):
if p < r:
q = partition(A, p, r)
_quicksort(A, p, q)
_quicksort(A, q + 1, r)
_quicksort(L, 0, ln)
if __name__ == '__main__':
import sys
import random
num = 100
if len(sys.argv) == 2:
num = int(sys.argv[1])
L = [ random.randrange(10, 1000) for x in range(num) ]
print L
quicksort(L)
print L
|
阅读(1165) | 评论(0) | 转发(0) |
