原理
归位
代码实现
def partition(li, left, right): # 将第一个数归位，即该数左边均小于它，右边均大于它
tmp = li[left] # 取出该值，当作该位置为空位
while left < right: # 左右交替查找直到重合，重合位置就是归位的位置
while left < right and li[right] >= tmp: # 从右往左查找直到出现小于该数的值
right -= 1
li[left] = li[right] #将小于该数的值填到左边空位，右边变成空位
while left < right and li[left] <= tmp: # 从左往右查找指导出现大于该数的值
left += 1
li[right] = li[left] # 将大于该数的值填到右边空位，左边变成空位
li[left] = tmp
return left # 返回归位的位置，将列表分为两个部分
def quick_sort(li,left,right):
if left < right: # 至少两个元素
mid = partition(li,left,right) # 将第一个数归位，返回索引位置
quick_sort(li,left,mid-1) # 将列表分为两部分，一部分都是小于第一个数
quick_sort(li,mid+1,right) # 另一部分都是大于第一个数，再递归进行归位
li = [5,7,4,6,3,1,2,9,8]
print(li)
quick_sort(li,0,len(li)-1)
print(li)
快排时间复杂度：O(nlogn)
快排最坏情况及解决办法
最快情况是：逆序列表，例如：[9,8,7,6,5,4,3,2,1]
解决办法：随机找列表中的一个数与第一个数交换位置，再进行归位。