|
#!/usr/bin/env python
from random import randrange as RANDOM
def split(A,low,high):
priov = A[low]
i = low
for j in range(low+1,high+1):
if A[j] <= priov :
i = i + 1
if i != j :
A[i],A[j] = A[j],A[i]
A[low],A[i] = A[i],A[low]
return i
def random_split(A,low,high):
i = RANDOM(low,high+1)
A[i],A[low] = A[low],A[i]
return split(A,low,high)
def quicksort(A,low,high):
if low < high :
w = random_split(A,low,high)
quicksort(A,low,w-1)
quicksort(A,w+1,high)
if __name__ == '__main__':
A = [1,5,3,9,2]
low = 0
high = len(A)-1
print 'before quicksort,the sequence is %s'% A
quicksort(A,low,high)
print 'after quicksort ,the sequence is %s' % A
|
