选择算法的最坏情况运行时间为线性时间，并提供其Python实现。

    import random
    import math
    #returns the number of elements that smaller than x
    #the input is A[p...r] inclusive in the convention of book,  1 <= p <= r <= n
    #in Python, to represent A[p...r], we should use a[p-1:r] 
    def partition(a,p,r,x):
    low = [m for m in a if m < x]
    high = [m for m in a if m > x]
    a[p-1:r] = low + [x] + high 
    return len(low)
    
    def median(a):
    a.sort()
    return a[(len(a)+1)/2 - 1]
    
    #x is the ith smallest element means there are (i-1) elements smaller than x
    #x is the 1st smallest means x is th