关键点

• 将第一个元素放到中间的位置，使得左边都小于它，右边都大于它

• 第一个元素的左边和右边，按照步骤一递归

  
  

尝试代码实现

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)

def partition(li,left,right):
    tmp = li[left]
    while left < right: #从右边取值放左边空位，从左边取值放右边空位。这样不断循环。
        while li[right] >= tmp:
            right -= 1
        li[left] = li[right]
        while li[left] <= tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left

运行后发现，报错了：

while li[right] >= tmp:
IndexError: list index out of range

从第一趟排序过程走一遍，发现并不满足左边比5小，右边比5大：

一开始的示例图是我们预期的情况，看下实际代码执行，left和right相遇时，left指向的空位其实是有值的，因为值比5小，所以left继续向右走，导致最后5的顺序错误

代码修正

确保left < right

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)

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

时间复杂度

普通情况下复杂度

共logn层，粗略假设每层大概插入的位置在中间左右，每次调用partition()后，下次的基数比原来少一半左右。但是每层的复杂度加起来仍然是O(n)
复杂度是：O(nlogn)

最坏情况下复杂度

li = [10,9,8,7,6,5,4,3,2,1]排序时，第一次排序结果：
第一次结果：

def quick_sort(li,left,right):
    if left < right:
        mid = partition(li,left,right) #li=[10,9,8,7,6,5,4,3,2,1]，left=0,right=9。返回mid=9
        quick_sort(li,left,mid-1) #li=[1,9,8,7,6,5,4,3,2,10]，left=0,right=8
        quick_sort(li,mid+1,right)#li=[1,9,8,7,6,5,4,3,2,10]，left=10,right=9

第一次调用partition()后，左边还有9个数，右边0个，接下来也类似，每次都只减少1个数。容易导致超过最大递归深度

复杂度是：O(n^2)

解决最坏情况下的最大递归深度问题

left元素向后随机取数，和left指向的元素交换。随机取数为最大值概率比较低，这样就极大地避免每次排序后只减少一个数，即减少最大递归深度错误的出现。

import random

def quick_sort(li,left,right):
    if left < right:
        mid = random_partition(li,left,right)
        quick_sort(li,left,mid-1)
        quick_sort(li,mid+1,right)

#left元素向后随机取数，和left指向的元素交换
def random_partition(li,left,right):
    i = random.randint(left,right)
    li[i],li[left] = li[left],li[i]
    mid = partition(li,left,right)
    return mid


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_sort2(li):
    if len(li) < 2:
        return li
    tmp = li[0]
    left = [value for value in li[1:] if value <= tmp]
    right = [value for value in li[1:] if value > tmp]
    left = quick_sort2(left)
    right = quick_sort2(right)
    return left + [tmp] + right