【什么叫快速排序】快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）于1960年提出。它采用分治策略（Divide and Conquer），通过选择一个“基准值”（pivot），将待排序的数组分为两部分：一部分比基准值小，另一部分比基准值大，然后递归地对这两部分进行排序，最终得到一个有序数组。
快速排序在实际应用中非常广泛，尤其在处理大规模数据时表现优异。其时间复杂度平均为 O(n log n)，最坏情况下为 O(n²)，但通过合理选择基准值可以避免最坏情况的发生。
快速排序核心步骤总结
| 步骤 | 描述 |
| 1. 选择基准值 | 从数组中选择一个元素作为基准值（通常可以选择第一个、最后一个或中间元素，或者随机选择）。 |
| 2. 分区操作 | 将数组中的元素划分为两个子数组：小于基准值的元素放在左边，大于基准值的元素放在右边。 |
| 3. 递归排序 | 对左右两个子数组分别重复上述步骤，直到子数组长度为1或0，此时视为已排序。 |
快速排序特点
| 特点 | 说明 |
| 时间复杂度 | 平均 O(n log n)，最坏 O(n²) |
| 空间复杂度 | O(log n)（递归栈开销） |
| 是否稳定 | 不稳定（相同元素顺序可能改变） |
| 是否原地排序 | 是（不需要额外存储空间） |
| 适用场景 | 大规模数据排序，尤其是内存有限的情况下 |
快速排序示例（以数组 [5, 3, 8, 4, 2] 为例）
1. 选择基准值：假设选中间元素 4。
2. 分区后：[2, 3] 和 [5, 8
3. 递归排序左半部分 [2, 3] → 已有序
4. 递归排序右半部分 [5, 8] → 已有序
5. 最终结果：[2, 3, 4, 5, 8
快速排序优缺点
| 优点 | 缺点 |
| 排序速度快，效率高 | 最坏情况下性能差 |
| 原地排序，节省内存 | 不稳定排序 |
| 实现简单，易于理解 | 需要合理选择基准值 |
总结
快速排序是一种基于分治思想的高效排序算法，适用于大多数需要排序的场景。虽然其最坏情况下的时间复杂度较高，但通过优化基准值的选择（如三数取中法），可以显著提升其性能。对于大多数实际应用来说，快速排序是一个非常实用且高效的排序方法。