代碼如下:
# -*- coding: utf-8 -*-

from random import randint
from math import ceil, floor

def _partition(A, l, r, i):
    """以A[i]為主元劃分?jǐn)?shù)組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 # 索引標(biāo)記
    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小的數(shù)，k in [l+1,r+1]：

    其尾遞歸方式，偽碼如下：
    SELECT(A, l, r, k)
    1  while true:
    2    i ← ? // 劃分主元位置
    3    m ← PARTITION(A, l, r, i) // 數(shù)組劃分
    4    n ← m - l + 1 // A[l..m]元素個數(shù)
    5    if k = n // 檢查A[m]是否是第k小的元素
    6      then return A[m]
    7    elseif k < n // 左劃分區(qū)
    8      r = m - 1
    9    else // 右劃分區(qū)
    10     k = k - n
    11     l = m + 1

    Args:
        pivot_selector(Function): 主元選取方法，默認(rèn)隨機方式
    """
    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