【什么叫快速排序】快速排序（Quick Sort）是一种高效的排序算法，采用分治策略对数据进行排序。它由英国计算机科学家托尼·霍尔（Tony Hoare）于1960年提出，是目前应用最广泛的排序算法之一。
快速排序的核心思想是：选择一个“基准”元素，将数组分为两个子数组，左边的元素都小于基准，右边的元素都大于基准，然后递归地对左右子数组进行排序。这种方法使得每次排序都能将数据分成更小的部分，从而逐步完成整个数组的排序。
快速排序总结
| 项目 | 内容 |
| 算法类型 | 分治排序算法 |
| 时间复杂度 | 平均 O(n log n)，最坏 O(n²) |
| 空间复杂度 | O(log n)（递归栈） |
| 稳定性 | 不稳定 |
| 是否原地排序 | 是（不需要额外空间） |
| 适用场景 | 数据量较大、需要高效排序时 |
| 基本思想 | 选取基准，分区排序，递归处理子数组 |
快速排序的步骤
1. 选择基准：从数组中选择一个元素作为基准（pivot）。
2. 分区操作：将数组中的元素分为两部分，一部分小于基准，另一部分大于基准。
3. 递归排序：对左右两个子数组重复上述过程，直到子数组长度为1或0，此时视为已排序。
快速排序的优点
- 速度快：在平均情况下比其他排序算法如冒泡排序、插入排序等更快。
- 空间效率高：不需要额外的存储空间，属于原地排序。
- 实现简单：逻辑清晰，容易理解与实现。
快速排序的缺点
- 最坏情况性能差：当输入数组已经有序时，时间复杂度退化为 O(n²)。
- 不稳定：相同值的元素可能在排序后顺序发生变化。
如何优化快速排序？
- 随机选择基准：避免最坏情况发生。
- 三数取中法：选取第一个、中间和最后一个元素的中位数作为基准。
- 小数组切换排序方法：当子数组较小时，使用插入排序更高效。
通过合理的选择基准和优化策略，快速排序可以在大多数实际应用场景中表现出色，成为排序算法中的首选之一。
