快速选择-递归排序
c=0
def quick_sort(lista, first, last):
global c
# 递归的退出条件
# print(lista)
if first >= last:
return
# 设定起始元素为要寻找位置的基准元素
mid_value = lista[first]
# low为序列左边的由左向右移动的游标
# high为序列右边的由右向左移动的游标
low = first
hight = last
while low < hight:
# 当hight位的值大于mid_value的值则一直向左移动
while low < hight and lista[hight] >= mid_value:
hight -= 1
c+=1
# 停止移动要么low与hight重合,要么到了hight位值小于mid_value
lista[low] = lista[hight]
while low < hight and lista[low] < mid_value:
low += 1
c+=1
lista[hight] = lista[low]
# hight -= 1
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
lista[low] = mid_value
# 在做递归的时候没有用切片,是为了保证在做多次递归的时候操作排序的永远只会是这一个列表
# 先对标志位左边的先进行排序
# print(lista)
quick_sort(lista, first, low-1)
# 再对标志位右边的先进行排序
quick_sort(lista, low+1, last)
return lista
print(quick_sort(lista,0, len(lista)-1))
print(c)
