当序列已经排好序时，将出现最差情况，时间复杂度降为O(n²)
随机快排用于解决序列近乎有序时算法复杂度退化为O(n²)的问题
from random import shuffle, randrange
def quick_sort(lst, left, right):
# 当只有一个元素的时候退出递归
if left < right:
p = partition(lst, left, right)
# 左右分区分别递归
quick_sort(lst, left, p)
quick_sort(lst, p+1, right)
def partition(lst, left, right):
rand = randrange(left, right)
lst[right-1], lst[rand] = lst[rand], lst[right-1] # 随机挑选出一个元素，与最后一个元素交换，作为分区点
pivot = lst[right-1] # 以最后一个元素为分区点
i = left - 1 # -1
for j in range(left, right): # range(0,10) [0..9]
# 如果小于分区点，则与i+1交换
if lst[j] < pivot:
i += 1
lst[i], lst[j] = lst[j], lst[i]
# 将pivot放入分区点(i+1)，与前半部分的下一个元素交换
if lst[right-1] < lst[i+1]:
lst[i+1], lst[right-1] = lst[right-1], lst[i+1]
# 返回分区点索引
return i+1
source = list(range(10))
shuffle(source)
quick_sort(source, 0, len(source))
print(source)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]