快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法一、递归实现的主框架

快速排序是一种高效的排序算法，由英国计算机科学家Tony Hoare在1962年提出。它基于“分而治之”的策略，其基本思想是选择一个基准元素（pivot），将数组分为两部分，一部分所有元素都小于基准，另一部分所有元素都大于或等于基准。然后对这两部分分别进行递归排序。

递归实现的主框架通常包括以下几个步骤：
1. **分区操作** (Partitioning): 从数组中选择一个基准值（通常是第一个或最后一个元素），把数组分为两个子数组。一个子数组的所有元素都小于基准，另一个子数组包含剩余元素（包括等于基准的）。
2. **递归调用** (Recursive Call): 对左右两个子数组分别进行同样的快速排序过程，直到子数组只剩下一个元素或为空，此时排序完成。
3. **合并结果** (Combining Results): 当所有的递归调用结束后，整个数组就被排序了。

以下是快速排序的伪代码形式：

def quicksort(arr):
    if len(arr) <= 1:
        return arr   # 基线条件：如果数组只有一个元素或为空，直接返回
    pivot = arr[len(arr) // 2]  # 选取基准
    less = [x for x in arr if x < pivot]  # 小于基准的元素
    equal = [x for x in arr if x == pivot]  # 等于基准的元素
    greater = [x for x in arr if x > pivot]  # 大于基准的元素
    return quicksort(less) + equal + quicksort(greater)