快速排序的python实现

快速排序

快速排序是利用了分治的思想，将数组分为两个部分，分别进行排序，然后合并。

在学习快速排序之前，需要先了解一道题：荷兰国旗问题

荷兰国旗问题

给定一个数组arr,和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

思路

1. 定义三个指针，分别指向小于num的数less(初始为left-1)，当前指向的数cur( 初始为left)，大于num的数more(初始为right+1)
2. 循环判断，如果cur小于num，则less++，cur++
3. 循环判断，如果cur大于num，则more--
4. 循环判断，如果cur等于num，则cur++
5. 当left >= right时，结束循环

快速排序

1. 随机选择一个数，作为基准数
2. 以基准数作为荷兰国旗问题的num，将数组分为三个部分
3. 递归调用，对小于基准数的部分进行快速排序
4. 递归调用，对大于基准数的部分进行快速排序
5. 直到子数组的长度为1，结束递归

代码实现

def quick_sort_3_0(arr: List) -> None:
    def partition(arr: List, left: int, right: int, num: int) -> int:
        less = left - 1
        more = right + 1
        while left < more:
            if arr[left] < num:
                arr[less + 1], arr[left] = arr[left], arr[less + 1]
                less += 1
                left += 1
            elif arr[left] > num:
                arr[more - 1], arr[left] = arr[left], arr[more - 1]
                more -= 1
            else:
                left += 1
        return less + 1, more - 1
    
    def recursion(left: int, right: int) -> None:
        if left >= right:
            return
        pivot_index = random.randint(left, right)  
        pivot = arr[pivot_index]  
        arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
        less, more = partition(arr, left, right, pivot)
        recursion(left, less - 1)
        recursion(more + 1, right)

    recursion(0, len(arr) - 1)

复杂度分析

快速排序的时间复杂度最差为O(N^2)，但由于快速排序使用了随机数，通过计算数学期望，时间复杂度为O(NlogN)