【什么叫快速排序】快速排序（Quick Sort）是一种高效的排序算法，采用分治策略来对数组进行排序。它通过选择一个“基准值”（pivot），将数组分为两个子数组：一个包含比基准值小的元素，另一个包含比基准值大的元素，然后递归地对这两个子数组进行排序。
快速排序在平均情况下具有较高的效率，时间复杂度为 O(n log n)，但在最坏情况下（如数组已有序）可能退化为 O(n²)。尽管如此，由于其在实际应用中的高效性，快速排序仍然是许多编程语言内置排序算法的基础。
快速排序总结
| 项目 | 内容 |
| 名称 | 快速排序（Quick Sort） |
| 类型 | 比较排序、分治算法 |
| 适用数据结构 | 数组、列表等线性结构 |
| 时间复杂度 | 平均 O(n log n)，最坏 O(n²) |
| 空间复杂度 | O(log n)（递归栈） |
| 稳定性 | 不稳定 |
| 是否原地排序 | 是（不需额外存储空间） |
| 核心思想 | 分治法，选择基准值，划分左右子数组，递归排序 |
| 优点 | 速度快，实现简单，适合大规模数据 |
| 缺点 | 最坏情况性能差，不稳定 |
快速排序的基本步骤
1. 选择基准值：从数组中选择一个元素作为基准。
2. 分区操作：将数组中所有小于基准的元素移到左边，大于基准的元素移到右边。
3. 递归排序：对左右两个子数组重复上述过程，直到子数组长度为0或1。
示例（以数组 [5, 3, 8, 4, 2] 为例）
1. 选择基准值（例如选第一个元素 5）。
2. 将小于 5 的元素移到左边，大于 5 的移到右边 → [3, 2, 4, 5, 8
3. 对左子数组 [3, 2, 4] 和右子数组 [8] 递归排序。
4. 最终结果为 [2, 3, 4, 5, 8
总结
快速排序是一种基于分治策略的高效排序算法，虽然在最坏情况下性能不佳，但其平均效率高、实现简单，是实际应用中非常受欢迎的排序方法之一。理解其原理和实现方式，有助于在不同场景下灵活使用。
