【快速排序是什么】快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）于1960年提出。它基于分治策略（Divide and Conquer），通过选择一个“基准值”（pivot），将数组分为两个子数组：一个包含比基准值小的元素，另一个包含比基准值大的元素，然后递归地对这两个子数组进行排序。
一、快速排序的基本思想
| 步骤 | 内容 |
| 1. 选择基准值 | 在待排序数组中选择一个元素作为基准值（通常选第一个、最后一个或中间的元素） |
| 2. 分割数组 | 将数组中所有小于基准值的元素移到左边，大于基准值的元素移到右边 |
| 3. 递归排序 | 对左右两个子数组重复上述过程，直到每个子数组只有一个元素为止 |
二、快速排序的特点
| 特点 | 描述 |
| 时间复杂度 | 平均情况为 O(n log n)，最坏情况下为 O(n²)（当每次选择的基准值都是最大或最小值时） |
| 空间复杂度 | O(log n)（递归调用栈的空间） |
| 稳定性 | 不稳定（相同元素的相对位置可能改变） |
| 适用场景 | 适用于大规模数据排序，尤其在实际应用中表现优异 |
| 优点 | 排序速度快，实现简单，内存使用少 |
| 缺点 | 最坏情况性能较差，需要合理选择基准值以避免退化 |
三、快速排序的实现步骤（伪代码）
```plaintext
function quickSort(array, left, right)
if left < right
pivotIndex = partition(array, left, right)
quickSort(array, left, pivotIndex - 1)
quickSort(array, pivotIndex + 1, right)
function partition(array, left, right)
pivot = array[right]// 选择最后一个元素作为基准
i = left - 1
for j from left to right - 1
if array[j] <= pivot
i = i + 1
swap array[i] and array[j
swap array[i+1] and array[right
return i + 1
```
四、快速排序与其它排序算法的对比
| 排序算法 | 时间复杂度（平均） | 空间复杂度 | 稳定性 | 适用场景 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 | 大规模数据排序 |
| 归并排序 | O(n log n) | O(n) | 稳定 | 需要稳定排序的场景 |
| 堆排序 | O(n log n) | O(1) | 不稳定 | 内存有限且需高效排序 |
| 插入排序 | O(n²) | O(1) | 稳定 | 数据量小或接近有序 |
五、总结
快速排序是一种高效的排序算法，具有较高的平均效率和较低的空间消耗。尽管其最坏情况下的时间复杂度较高，但通过合理的基准值选择（如随机化或三数取中法），可以有效避免这一问题。在实际编程中，快速排序被广泛应用于各种排序任务中，是学习算法和理解分治思想的重要内容之一。
