【什么叫快速排序】快速排序（Quick Sort）是一种高效的排序算法，采用分治策略对数据进行排序。它的基本思想是选择一个“基准”元素，将数组分为两部分：一部分比基准小，另一部分比基准大，然后递归地对这两部分进行排序。
一、快速排序的基本步骤
| 步骤 | 操作说明 |
| 1 | 从数组中选择一个基准元素（通常选第一个、最后一个或中间的元素） |
| 2 | 将数组中所有小于基准的元素移到左边，大于基准的元素移到右边 |
| 3 | 对左右两个子数组重复上述过程，直到每个子数组只剩一个元素 |
二、快速排序的特点
| 特点 | 描述 |
| 时间复杂度 | 平均为 O(n log n)，最坏为 O(n²)（当数组已有序时） |
| 空间复杂度 | O(log n)（递归调用栈） |
| 稳定性 | 不稳定（相同值的元素可能交换位置） |
| 适用场景 | 适用于大规模数据排序，尤其是内存有限的情况 |
三、快速排序的优点与缺点
| 优点 | 缺点 |
| 排序速度快，效率高 | 最坏情况下性能较差 |
| 原地排序，空间占用少 | 不稳定，可能打乱相同元素的顺序 |
| 实现简单，易于理解 | 需要合理选择基准以避免最坏情况 |
四、示例说明
假设有一个无序数组：`[5, 3, 8, 4, 2]`
1. 选择基准为 `5`
2. 将比 `5` 小的数放在左边，大的放在右边 → `[3, 2, 5, 8, 4]`
3. 对左子数组 `[3, 2]` 和右子数组 `[8, 4]` 分别递归排序
4. 最终得到有序数组：`[2, 3, 4, 5, 8]`
五、总结
快速排序是一种基于分治思想的高效排序方法，具有较高的平均效率和较低的空间消耗。虽然在某些极端情况下性能不佳，但通过合理选择基准（如随机选择或三数取中），可以有效避免最坏情况的发生。它广泛应用于实际编程中，尤其适合处理大规模数据集。
