书店手机网站模板,国外做免费网站的,收录查询 站长工具,wordpress 配置一、快速排序
1、快速排序总结 快速排序是一种高效的排序算法#xff0c;基于分治法的思想。 分区操作是快速排序的核心#xff0c;将数组分为两部分。 原地分区可以减少空间复杂度#xff0c;提高效率。 快速排序的平均时间复杂度为 O(n log n)#xff0c;但在最坏情况…一、快速排序
1、快速排序总结 快速排序是一种高效的排序算法基于分治法的思想。 分区操作是快速排序的核心将数组分为两部分。 原地分区可以减少空间复杂度提高效率。 快速排序的平均时间复杂度为 O(n log n)但在最坏情况下如输入数组已经排序会退化到 O(n²)。 2、快速排序的基本思路 选择基准值Pivot 从数组中选择一个元素作为基准值。基准值的选择可以是数组的第一个元素、最后一个元素、中间元素或者随机选择。 分区操作Partition 将数组分为两部分 一部分包含小于基准值的元素。 另一部分包含大于基准值的元素。 基准值最终会放在它最终的位置上。 递归排序 对小于基准值的部分递归调用快速排序。 对大于基准值的部分递归调用快速排序。 合并结果 由于分区操作已经将数组分为两部分递归排序后数组自然有序无需额外的合并操作。
3、快速排序和冒泡排序的区别 冒泡排序 优点实现简单代码量少。 缺点效率低时间复杂度为 O(n²)不适用于大规模数据。 快速排序 优点效率高平均时间复杂度为 O(n log n)适合大规模数据。 缺点实现相对复杂不稳定排序算法。 二、代码
def quick_sort(arr):# 如果数组长度小于等于1直接返回if len(arr) 1:return arr# 选择基准值这里选择最后一个元素pivot arr[-1]# 分区操作left [x for x in arr[:-1] if x pivot] # 小于等于基准值的元素right [x for x in arr[:-1] if x pivot] # 大于基准值的元素# 递归排序左右两部分并拼接结果return quick_sort(left) [pivot] quick_sort(right)# 示例
nums [3, 2, 1, 5, 6, 4]
sorted_nums quick_sort(nums)
print(sorted_nums) # 输出[1, 2, 3, 4, 5, 6]
