万户网络做网站怎么样品牌推广平台
一、快速排序
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]