快排采用分治递归策略，从待排序数组选一个基准值，比如首元素，然后剩下的元素里，比基准值小的放左边，大的放右边。这两部分继续递归进行排序。
首元素做基准
def quick_sort(lst):
length = len(lst)
if length <= 1:
return lst
key = lst[0] # 选第一个作为基准值
left = [lst[i] for i in range(1, length) if lst[i] < key] # 比基准值小的放左边
right = [lst[i] for i in range(1, length) if lst[i] >= key] # 比基准值大的放右边
return quick_sort(left) + [key] + quick_sort(right)
末元素做基准
也可以选择末元素做基准值，这样可以pop删掉再循环，代码简洁了些。当然也可以选择中位值作为基准值。
def quick_sort(lst):
length = len(lst)
if length <= 1:
return lst
key = lst[-1] # 选最后一个作为基准值
lst.pop()
left = [i for i in lst if i < key] # 比基准值小的放左边
right = [i for i in lst if i >= key] # 比基准值大的放右边
return quick_sort(left) + [key] + quick_sort(right)
优化比较次数
上面的代码一目了然，比较pythonic，但是在划分左右的时候比较次数重复了，比基准值小的没必要再去比较是否比基准值大，可以优化。
key = lst[0]
left, right = [], []
for i in range(1, length):
if lst[i] < key:
left.append(lst[i])
else:
right.append(lst[i])
原地调整数组
之前的代码都开辟新数组，能否直接原地inplace排序？这是我们见得比较多的快排的一个版本，设置左右指针往中间靠拢。
def quick_sort(lst, left=0, right=None):
if not left:
left = 0
if not right:
right = len(lst) - 1
if right - left < 1:
return
# 保存分治的边界
low = left
high = right
key = lst[left] # 左值作为基准保存
while left < right:
while lst[right] >= key and left < right: # 从右边开始找第一个比基准值小的，注意，必须先看右边的，因为左值是基准！
right -= 1
lst[left] = lst[right] # 右值赋值给左值， 首位（左）、右分别为 小、小
while lst[left] <= key and left < right: # 从左边开始找第一个比基准值大的
left += 1
lst[right] = lst[left] # 左值赋值给右值，至此，左右互换一次，首位、左、右分别为 小、大、大
else:
lst[left] = key # 左右相撞，赋值为基准值，首位、左、右分别为 小、基、大
quick_sort(lst, low, left - 1)
quick_sort(lst, left + 1, high)
其实这个代码我觉得有点拗口，可以理解为基准值往中间冒泡。
非递归版本
采用堆栈
def quick_sort(lst):
if len(lst) <= 1:
return lst
stack = []
stack.append(len(lst) - 1)
stack.append(0)
while stack:
left = stack.pop()
right = stack.pop()
low = left
high = right
key = lst[left]
while left < right:
while lst[right] >= key and left < right:
right -= 1
lst[left] = lst[right]
while lst[left] <= key and left < right:
left += 1
lst[right] = lst[left]
else:
lst[left] = key
if low < left - 1:
stack.append(left - 1)
stack.append(low)
if high > left + 1:
stack.append(high)
stack.append(left + 1)
时间复杂度
如果每次都能二等分，属于最优，那么就是O(nlgn)；最差情况是每次都没分开，那么就是O(n²)。另外，平均时间复杂度也是O(nlgn)，证明比较复杂。
