import random

def PARTTION(A,p,r):

    x = A[r]

    i = p -1

    for j in range(p,r):

        if A[j] <= x:

            i += 1

            A[j],A[i] = A[i],A[j]

    i += 1

    A[r],A[i] = A[i],A[r]

    print(x,A)

    return i

def RANDOMIZED_PARTITION(A,p,r):

    #主元随机化处理

    t = random.randint(p,r)

    A[t],A[r] = A[r],A[t]

    return PARTTION(A,p,r)

def RANDOMIZED_SELECT(A,p,r,i):

    #A 要查找的list

    #p 左边界

    #r 右边界

    #i 值[p,r]中第i位

    if p == r: #只有一位

        return A[p]

    q = RANDOMIZED_PARTITION(A,p,r) #快排关键代码 分成俩半

    k = q - p + 1

    if i == k:

        return A[q]

    elif i < k:

        return RANDOMIZED_SELECT(A,p,q-1,i)

    else:

        return RANDOMIZED_SELECT(A,q+1,r,i-k)

if __name__ == "__main__":

    A = [89, 100, 21, 5, 2, 8, 33, 27, 63]

    print(RANDOMIZED_SELECT(A,0,len(A)-1,2)) #查找第二位

'''

>>>

=========== RESTART: F:/python/algorithms/9_3_randomized_select.py ===========

63 [21, 5, 2, 8, 33, 27, 63, 100, 89]

21 [5, 2, 8, 21, 33, 27, 63, 100, 89]

5 [2, 5, 8, 21, 33, 27, 63, 100, 89]

5

win7+python3.5.1

>>>

'''