def partition(A,p,r):
x=A[r]
i=p-1
j=0
for j in range(p,r):
if(A[j]<=x):
i=i+1
exchange(A,i,j)
exchange(A,i+1,r)
return i+1
def exchange(A,i,j):
itar=A[i]
A[i]=A[j]
A[j]=itar
def quicksort(A,p=0,r=None):
if(r==None):
r=len(A)-1
if(p<r):
q=partition(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)
快速排序 的 时间复杂度 的数学期望 是 nlgn