快速排序

---

快排思路：

1. 取第一个元素p，使元素p归位
2. 列表被p分成两部分，左边都比p小，右边都比p大
3. 递归完成排序

我们先搞定p归位的函数partition函数，然后左右两边的部分再去递归调用partition函数就得到最终目标了。

partition函数代码实现

def partition(li, left, right):
    # 思路: 归为必须从左边high开始，看动图（p是在列表第一位抽出来的， 所有从后面开始比较）

    tmp = li[left]

    # 当left=right的时候，p回到中间的位置（左边的都比p小，右边都比p大）
    while left < right:

        while left < right and li[right] >= tmp:     # 从右边找比tmp小的数，只要找到的数>=tmp, 就一直找
            # left < right防止 left=right 的时候p值每归位，还往左走
            right -= 1
        li[left] = left[right]  # right原来位置上比tmp值小的值，要等下一层循环到的比tmp大的值填上
        
        while left < right and li[left] <= tmp:      # 从左边找比tmp大的数，只要找到的数<=tmp, 就一直找
            left += 1
        li[right] = li[left]
        
    # 归位
    li[left] = tmp
    
    return left

 写完partition函数之后就可以把quick_sort函数写出来了（问题拆分）:

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 = [1, 2, 5, 3, 4, 6, 9, 8, 7]

quick_sort(li, 0, len(li)-1)
print(li)

 小结：

1. 快排的时间复杂度为O（nlogn）
2. 用了递归，会有空间复杂度