1、算法步骤

① 从数列中挑出一个元素，称为 “基准”（pivot）;

② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

2、动图演示

3、代码

# 定义一个函数quickSort，参数为一个列表arr，以及可选的左右边界left和right
def quickSort(arr, left=None, right=None):
    # 如果左边界left不是整数或浮点数，则将其设为0
    left = 0 if not isinstance(left, (int, float)) else left
    # 如果右边界right不是整数或浮点数，则将其设为列表长度减1
    right = len(arr) - 1 if not isinstance(right, (int, float)) else right
    # 如果左边界小于右边界，则继续进行快速排序
    if left < right:
        # 获取分区点的索引
        partitionIndex = partition(arr, left, right)
        # 对分区点左边的部分进行快速排序
        quickSort(arr, left, partitionIndex - 1)
        # 对分区点右边的部分进行快速排序
        quickSort(arr, partitionIndex + 1, right)
    # 返回排序后的列表arr
    return arr

# 定义一个函数partition，用于确定分区点的索引
def partition(arr, left, right):
    # 将最左边的元素作为基准值
    pivot = left
    index = pivot + 1
    i = index
    # 循环遍历数组，将小于基准值的元素移到基准值左边
    while i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index += 1
        i += 1
    # 将基准值与最后一个小于基准值的元素交换位置
    swap(arr, pivot, index - 1)
    # 返回分区点的索引
    return index - 1

# 定义一个函数swap，用于交换数组中两个元素的位置
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

打赏 支付宝打赏 微信打赏