Python全系列 教程
3567个小节阅读:5929k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本,未来主流的版本
人工智能 教程
顺势而为,AI创新未来
大厂算法 教程
算法,程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
快速排序(Quicksort)是一种基于分治策略的排序算法,运行高效,应用广泛
从数列中挑出一个元素,称为 “基准”(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