def PARTITION(A,p,r):

    x = A[r] # 锚点 主元{大于它放一边，小于的放另一边}

    i = p - 1

    for j in range(p,r):

        if A[j] <= x:

            i += 1

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

    A[i+1],A[r] = A[r],A[i+1]

    return i + 1

def QUICKSORT(A,p,r):

    if p < r: #分治

        q = PARTITION(A,p,r)

        QUICKSORT(A,p,q-1)

        QUICKSORT(A,q+1,r)

if __name__ == "__main__":

    A = [2,8,7,1,3,5,6,4]

    QUICKSORT(A,0,len(A)-1)

    print(A)

'''

=============== RESTART: F:/python/algorithms/7_1_quicksort.py ===============

[1, 2, 3, 4, 5, 6, 7, 8]

win7+python3.5.1

'''

import random

def PARTITION(A,p,r):

    x = A[r] # 锚点 主元{大于它放一边，小于的放另一边}

    i = p - 1

    for j in range(p,r):

        if A[j] <= x:

            i += 1

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

    A[i+1],A[r] = A[r],A[i+1]

    return i + 1

def RANDOMIZED_PARTITION(A,p,r):

    i = random.randint(p,r) #随机的变化

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

    return PARTITION(A,p,r)

def RANDOMIZED_QUICKSORT(A,p,r):

    if p < r: #分治

        q = RANDOMIZED_PARTITION(A,p,r)

        RANDOMIZED_QUICKSORT(A,p,q-1)

        RANDOMIZED_QUICKSORT(A,q+1,r)

if __name__ == "__main__":

    A = [2,8,7,1,3,5,6,4]

    RANDOMIZED_QUICKSORT(A,0,len(A)-1)

    print(A)

'''

=============== RESTART: F:/python/algorithms/7_1_quicksort.py ===============

[1, 2, 3, 4, 5, 6, 7, 8]

win7+python3.5.1

'''