快速排序_思路-【官方】百战程序员_IT在线教育培训机构

从数列中挑出一个元素，称为 “基准”(pivot)
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

举例

代码


xxxxxxxxxx
def quick_sort(data):
    if len(data)>=2:
        # 找到基准值
        mid = data[len(data)//2]
        # 建立2个列表来存储比基准值小，大的数据
        left,right=[],[]
        # 从原数据中，删除mid
        data.remove(mid)
        # 遍历原有数据
        for num in data:
            # 如果数据比基准值大，就存放到right
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        # 合并数据,注意合并时,不把 列表和数字进行拼接,所以把mid封装到一个列表中
        return quick_sort(left) + [mid] +quick_sort(right)
    else:
        return data

算法特性

时间复杂度 $ O(n \log n) $、自适应排序：在平均情况下，基数的递归层数为 $ \log n$ ，每层中的总循环数为 $n$ ，总体使用 $ O(n \log n) $ 时间。在最差情况下，每轮哨兵划分操作都将长度为 $ n $ 的数组划分为长度为 0 和 $ n-1 $ 的两个子数组，此时递归层数达到 $n$ ，每层中的循环数为 $n$ ，总体使用 $ O(n^2) $时间
空间复杂度 $ O(n) $、原地排序：在输入数组完全倒序的情况下，达到最差递归深度$ n $ ，使用 $ O(n) $栈帧空间。排序操作是在原数组上进行的，未借助额外数组
非稳定排序：基准数可能会被交换至相等元素的右侧


xxxxxxxxxx
def partition(nums: list[int], left: int, right: int) -> int:
    # 以 nums[left] 为基准数
    i, j = left,right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1  # 从右向左找首个小于基准数的元素
        while i < j and nums[i] <= nums[left]:
            i += 1  # 从左向右找首个大于基准数的元素
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
    # 将基准数交换至两子数组的分界线
    nums[i], nums[left] = nums[left], nums[i]
    return i  # 返回基准数的索引

def quick_sort(nums: list[int], left: int, right: int):
    """快速排序"""
    # 子数组长度为 1 时终止递归
    if left >= right:
        return
    # 哨兵划分
    pivot = self.partition(nums, left, right)
    # 递归左子数组、右子数组
    self.quick_sort(nums, left, pivot - 1)
    self.quick_sort(nums, pivot + 1, right)

实时效果反馈

1. 关于快速排序算法，说法正确的是？

A 快速排序需要将数列分成若干个子序列，在合并时排序

B 快速排序每一轮都要俩俩比较元素

C 快速排序每次分割会分成2部分数据

D 快速排序需要将数列分成若干个子序列，在分割时排序

答案

1=>D

Python入门

北京市昌平区回龙观镇南店村综合商业楼2楼226室