快速排序-递归排序
每次把第一个数设为中间值，比它大的放右边的列表，比它小的放左边的列表。如果列表长度小于2，则返回列表。对每个子列表递归排序
def quick_sort(lst):
if len(lst)<2:
return lst
# print(lst)
r=[]
l=[]
k=lst[0]
# print(k)
for i in range(1,len(lst)):
if lst[i]>=k:
r.append(lst[i])
else:
l.append(lst[i])
return quick_sort(l)+[k]+quick_sort(r)
缺点，要建两个临时列表，占用空间
改进：原地排序，不占用新空间
def quick_sort(lista, first, last):
if first >= last:
return
mid_value = lista[first]
low = first
hight = last
while low < hight:
while low < hight and lista[hight] >= mid_value:
hight -= 1
lista[low] = lista[hight]
while low < hight and lista[low] < mid_value:
low += 1
lista[hight] = lista[low]
lista[low] = mid_value
quick_sort(lista, first, low-1)
quick_sort(lista, low+1, last)
return lista
