个人技术博客地址：http://songmingyao.com/
原理
- 在列表中挑选出一个基准值
- 将列表中的其它元素与基准值对比，比基准值大的放在基准值右侧，比基准值小的放在基准值左侧
- 以此类推
源码
def quick_sort(l, start, end):
if start >= end:
return
low = start
high = end
mid_value = l[low]
while low < high:
# low<high这个条件必须在这里再次体现，避免出现循环过程中low>high的情况
while low < high and l[high] >= mid_value:
high -= 1
# 当中间值右侧的值小于中间值时，将该值赋值于l[low](原来的值已保存至mid_value变量)
l[low] = l[high]
# low<high这个条件必须在这里再次体现，避免出现循环过程中low>high的情况
while low < high and l[low] <= mid_value:
low += 1
# 当中间值左侧的值大于中间值时，将该值赋值于l[high](原来的值已保存至l[low])
l[high] = l[low]
# 退出循环时，说明low==high，则可以将mid_value的值赋予它
l[low] = mid_value
quick_sort(l, start, low-1)
quick_sort(l, low+1, end)
if __name__ == '__main__':
l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
print(l)
quick_sort(l, 0, len(l)-1)
print(l)
时间复杂度
- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(n2)
- 稳定性（多个元素等值的情况下是否会破坏原有顺序）：不稳定
