Quick sort. Θ(nlgn)
2017-11-14 本文已影响18人
R0b1n_L33
from random import shuffle
def partition(array, p, r):
x = array[r]
i = p - 1
for j in range(p, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
i += 1
array[i], array[r] = array[r], array[i]
return i
def quickSort(array, p, r):
if p < r:
division = partition(array, p, r)
quickSort(array, p, division-1)
quickSort(array, division+1, r)
l = list(range(10))
shuffle(l)
print(l)
##############
quickSort(l, 0, len(l)-1)
##############
print(l)
