快速排序（quick-sort）

快速排序思路：

• 去一个元素p(列表中第一个元素)，是元素归位
• 列表被分为两部分，左边都比p小，右边都比p大
• 递归完成排序
  

partition函数：归位函数，算出中间值的下标位置

每一个partition函数的时间复杂度为logn，一共有n次

所以快速排序的时间复杂度为O(nlogn)（最好情况下）

def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:   #从右边找tmp小的数
            right -= 1          #往左走一步
        li[left] = li[right]    #把右边的值写道左边的空位上
        print(li, 'right')
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]   #把左边的值写道右边空位上
        print(li, 'left')
    li[left] = tmp       #两值相等之后把tmp归位
    return left       #返回mid的值

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]
quick_sort(li, 0, len(li)-1)
print(li)



#结果
[2, 7, 4, 6, 3, 1, 2, 9, 8] right
[2, 7, 4, 6, 3, 1, 7, 9, 8] left
[2, 1, 4, 6, 3, 1, 7, 9, 8] right
[2, 1, 4, 6, 3, 6, 7, 9, 8] left
[2, 1, 4, 3, 3, 6, 7, 9, 8] right
[2, 1, 4, 3, 3, 6, 7, 9, 8] left
[1, 1, 4, 3, 5, 6, 7, 9, 8] right
[1, 1, 4, 3, 5, 6, 7, 9, 8] left
[1, 2, 3, 3, 5, 6, 7, 9, 8] right
[1, 2, 3, 3, 5, 6, 7, 9, 8] left
[1, 2, 3, 4, 5, 6, 7, 9, 8] right
[1, 2, 3, 4, 5, 6, 7, 9, 8] left
[1, 2, 3, 4, 5, 6, 7, 9, 8] right
[1, 2, 3, 4, 5, 6, 7, 9, 8] left
[1, 2, 3, 4, 5, 6, 7, 8, 8] right
[1, 2, 3, 4, 5, 6, 7, 8, 8] left
[1, 2, 3, 4, 5, 6, 7, 8, 9]