快速排序是一种非常高效的、基于分治法的排序算法，它的平均时间复杂度为 O(n log n)，是实践中最常用的排序算法之一。

核心思想

快速排序的核心思想可以分解为三个步骤：

1. 选择基准：从数组中选择一个元素作为“基准”（pivot）。
2. 分区：重新排列数组，使得所有比基准值小的元素都移动到基准值的左边，所有比基准值大的元素都移动到基准值的右边，这个分区操作结束后，基准值就处于它最终排序好的位置上。
3. 递归：对基准值左右两个子数组递归地执行上述步骤，直到子数组的长度为 1 或 0，此时它们自然就是有序的。

Python 实现

下面是快速排序的几种常见 Python 实现方式，从最经典的递归版本到更 Pythonic 的列表推导式版本。

经典递归实现（Lomuto 分区方案）

这是最常见、最容易理解的实现方式，我们选择最后一个元素作为基准。

def quicksort(arr):
    """
    经典的快速排序递归实现 (Lomuto 分区方案)
    """
    # 基线条件：如果数组长度小于等于1，它已经是有序的
    if len(arr) <= 1:
        return arr
    else:
        # 选择最后一个元素作为基准
        pivot = arr[-1]
        # 分区过程
        # 1. 创建一个列表，存放所有比基准小的元素
        less = [x for x in arr[:-1] if x <= pivot]
        # 2. 创建一个列表，存放所有比基准大的元素
        greater = [x for x in arr[:-1] if x > pivot]
        # 递归调用，并将结果拼接起来
        return quicksort(less) + [pivot] + quicksort(greater)
# --- 使用示例 ---
my_list = [3, 6, 8, 10, 1, 2, 1]
sorted_list = quicksort(my_list)
print(f"原始列表: {my_list}")
print(f"排序后列表: {sorted_list}")
# 输出:
# 原始列表: [3, 6, 8, 10, 1, 2, 1]
# 排序后列表: [1, 1, 2, 3, 6, 8, 10]

代码解析:

• 基准: pivot = arr[-1]，我们选择最后一个元素。
• 分区: 使用列表推导式非常简洁地完成了分区。
  • less 包含了除了基准之外所有小于等于 pivot 的元素。
  • greater 包含了所有大于 pivot 的元素。
• 递归与合并: quicksort(less) 对左半部分排序，quicksort(greater) 对右半部分排序，然后将排序好的左半部分、基准和排序好的右半部分拼接起来。

优点:

• 代码简洁,易于理解。

缺点:

• 不够高效,在每次分区时，我们创建了 less 和 greater 两个新的列表，这会消耗额外的内存空间，空间复杂度在最坏情况下是 O(n)。

原地排序实现（Hoare 或 Lomuto 分区方案）

为了优化空间复杂度,我们可以实现“原地排序”，即直接在原始数组上进行交换，而不需要创建新的列表，这是面试中更受青睐的实现方式。

我们这里使用 Lomuto 分区方案，它更容易理解。

def quicksort_inplace(arr, low, high):
    """
    原地快速排序 (Lomuto 分区方案)
    arr: 待排序的列表
    low: 子数组的起始索引
    high: 子数组的结束索引
    """
    if low < high:
        # partition_index 是分区后基准值最终所在的位置
        partition_index = partition(arr, low, high)
        # 递归地对基准值左边的子数组进行排序
        quicksort_inplace(arr, low, partition_index - 1)
        # 递归地对基准值右边的子数组进行排序
        quicksort_inplace(arr, partition_index + 1, high)
def partition(arr, low, high):
    """
    Lomuto 分区函数
    选择最后一个元素作为基准，将小于基准的元素移到左边，大于的移到右边。
    返回基准值的最终索引。
    """
    pivot = arr[high]  # 选择最后一个元素作为基准
    i = low - 1  # i 是小于基准的区域的边界索引
    for j in range(low, high):
        # 如果当前元素小于或等于基准
        if arr[j] <= pivot:
            i += 1  # 扩展小于基准的区域
            arr[i], arr[j] = arr[j], arr[i]  # 交换元素
    # 将基准值放到正确的位置上 (i+1)
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
# --- 使用示例 ---
my_list = [3, 6, 8, 10, 1, 2, 1]
print(f"原始列表: {my_list}")
# 调用原地排序函数，需要提供初始的 low 和 high 索引
quicksort_inplace(my_list, 0, len(my_list) - 1)
print(f"排序后列表: {my_list}")
# 输出:
# 原始列表: [3, 6, 8, 10, 1, 2, 1]
# 排序后列表: [1, 1, 2, 3, 6, 8, 10]

代码解析:

• quicksort_inplace: 这个函数是递归的入口，它接收一个子数组的范围 [low, high]。
• partition: 这是核心的分区函数。
  • pivot = arr[high]: 选择最后一个元素为基准。
  • i: 指向最后一个小于等于 pivot 的元素的位置，初始化为 low - 1。
  • for j in range(low, high): 遍历从 low 到 high-1 的所有元素。
  • if arr[j] <= pivot: 如果找到一个小于等于基准的元素，就把它交换到 i+1 的位置，并扩展 i 的边界。
  • 将基准 arr[high] 与 arr[i+1] 交换，这样基准就位于它最终的位置上，i+1 就是它的索引。
• 递归: 调用 quicksort_inplace 分别处理基准左右两侧的子数组。

优点:

• 空间复杂度为 O(log n)（递归调用栈的深度），远优于第一种实现。
• 速度快，因为没有创建新列表的开销。

性能分析

• 时间复杂度:

  • 平均情况: O(n log n)，每次分区都将数组大致分成两半，递归树的高度为 log n，每层处理 n 个元素。
  • 最坏情况: O(n²)，当每次选择的基准都是当前数组的最小值或最大值时（对一个已经排序好的数组进行排序），分区会极度不平衡，递归树会退化成一个链表。
  • 最好情况: O(n log n)，每次基准都能完美地将数组对半分。

• 空间复杂度:

  • 经典实现: O(n)，因为每次递归都会创建新的列表。
  • 原地排序实现: O(log n)，主要消耗在递归调用栈的深度上，最坏情况下（O(n²)时间复杂度时），空间复杂度会退化为 O(n)。

如何避免最坏情况？

可以通过优化基准的选择来避免最坏情况，从而保证算法的稳定性。

1. 随机选择基准: 在分区前，随机选择一个元素与 arr[high] 交换。
2. 三数取中法: 选择 arr[low], arr[high], arr[mid] 三个元素的中位数作为基准。

对于 Python 虽然自己实现快速排序是很好的练习，但在实际项目中，应该始终使用内置的 list.sort() 方法或 sorted() 函数，因为它们是经过高度优化的 C 语言实现，并且在处理各种情况（包括已经排序或逆序的数据）时采用了更复杂的混合策略（如 Timsort 算法），性能通常比手写的 Python 版本要好得多。