快速排序算法详解：从理论到实践的全方位指导

一、算法基本概念

快速排序（Quicksort）是一种基于分治策略的高效排序算法，由Tony Hoare于1960年提出。其核心思想可以概括为三个步骤：

1. 分解：选取基准元素（pivot），将数组划分为两个子数组
2. 解决：递归地对子数组进行排序
3. 合并：将已排序的子数组进行组合

与归并排序不同，快速排序的关键在于原地排序（in-place）特性，即在排序过程中不需要额外的存储空间。这使得它在处理大规模数据时具有显著的内存优势。

二、算法实现步骤

2.1 基准元素选择

基准元素的选择直接影响算法效率，常见方法包括：

• 首元素法：直接选取第一个元素
• 随机法：随机选取元素
• 三数取中法：取首、中、尾三个元素的中位数

# 三数取中法实现
def median_of_three(arr, low, high):mid = (low + high) // 2if arr[low] > arr[mid]:arr[low], arr[mid] = arr[mid], arr[low]if arr[low] > arr[high]:arr[low], arr[high] = arr[high], arr[low]if arr[mid] > arr[high]:arr[mid], arr[high] = arr[high], arr[mid]return mid

2.2 分区操作

分区（Partitioning）是算法的核心步骤，其目标是将数组划分为两个部分：

$$\text{左侧}\le \text{pivot}\le \text{右侧}$$

标准分区过程：

1. 选取基准元素
2. 设置左右指针
3. 左指针右移直到找到大于pivot的元素
4. 右指针左移直到找到小于pivot的元素
5. 交换这两个元素
6. 重复3-5直到指针相遇

def partition(arr, low