【什么叫快速排序】快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）于1960年提出。它采用分治策略（Divide and Conquer），通过选择一个“基准值”（pivot），将数组分为两个子数组：小于基准值的元素和大于基准值的元素，然后递归地对这两个子数组进行排序，最终实现整个数组的有序排列。
快速排序的核心思想
| 步骤 | 说明 |
| 1. 选择基准值 | 从数组中选择一个元素作为基准值（可以是任意位置的元素，也可以通过特定方法选择） |
| 2. 分区操作 | 将数组中所有比基准值小的元素移到左边，比基准值大的元素移到右边 |
| 3. 递归排序 | 对左右两个子数组分别重复上述步骤，直到子数组长度为1或0，即视为已排序 |
快速排序的特点
| 特点 | 说明 |
| 时间复杂度 | 平均情况为 O(n log n)，最坏情况下为 O(n²)（当每次选择的基准值都是最大或最小值时） |
| 空间复杂度 | O(log n)（由于递归调用栈） |
| 稳定性 | 不稳定（相同元素的相对顺序可能改变） |
| 是否原地排序 | 是（不需要额外的存储空间） |
| 适用场景 | 适用于大规模数据的排序，尤其在实际应用中表现优异 |
快速排序的优缺点
| 优点 | 缺点 |
| 排序速度快，效率高 | 最坏情况下性能较差 |
| 原地排序，空间消耗少 | 需要合理选择基准值以避免最坏情况 |
| 实现简单，易于理解 | 对于小数据量不如插入排序等简单算法高效 |
快速排序的实现思路（伪代码）
```
function quickSort(arr, left, right):
if left < right:
pivotIndex = partition(arr, left, right)
quickSort(arr, left, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, right)
function partition(arr, left, right):
pivot = arr[right
i = left
for j from left to right - 1:
if arr[j] <= pivot:
swap arr[i] and arr[j
i = i + 1
swap arr[i] and arr[right
return i
```
总结
快速排序是一种基于分治策略的高效排序算法，其核心在于“分区”操作。虽然最坏情况下时间复杂度较高，但通过合理的基准值选择（如随机选择、三数取中法等），可以有效提升其性能。在实际应用中，快速排序因其高效性和原地排序特性，被广泛用于各种编程语言的标准库中。
