排序思路: 1、一般以数组中的第一个元素作为基准值
2、左游标右移,遇到比基准值大的停
3、又游标左移,遇到比基准值小的停
情况1:左游标< 右游标 左右游标互换位置
情况2:左游标> 右游标 右游标和基准值互换位置
def quick_sort(li,first,last):
# 递归出口
#基准值正确位置为0: split_position = 0
#first: 0
#last: spilt_position-1 = -1
if first > last:
return
#找到基准值的正确位置的下标索引
split_position = part(li,first,last)
#递归思想,左右两边继续执行快排
quick_sort(li,first,split_position -1)
quick_sort(li,split_position +1,last)
def part(li,first,last):
#给一个基准值找到正确位置
#first: 快速排序部分的第一个元素的下标索引
#last: 快速排序部分的第一个元素的下标索引
mid = li[first]
lcorsor = first + 1
rcorsor = last
sign = True
while sign:
#左游标右移
while lcursor <= rcursor and li[lcursor] <= mid:
lcorsor +=1
#右游标左移
while lcursor <= rcursor and li[rcursor] >= mid:
lcorsor -=1
if lcorsor < rcorsor:
#左右游标互换位置
li[lcorsor],li[rcorsor] = li[rcorsor],li[lcorsor]
else:
#右游标和基准值互换位置
li[first],li[rcorsor] = li[rcorsor],li[first]
#执行到这个分支,基准值的正确位置已找到,终止此循环
sign = False
return rcorsor