算法题：快速排序

一、快速排序

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]