快速排序
快速排序是一种高效的排序算法，采用分治策略。它选择一个基准元素，将数组分为两部分：小于基准的元素和大于基准的元素，然后递归地对这两部分进行排序。
算法原理
快速排序的基本思想是：选择一个基准元素，通过分区操作将数组分为两部分：一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。然后递归地对这两部分进行排序。当子数组的大小为0或1时，递归结束，整个数组就排好序了。
算法步骤
- 选择一个基准元素（通常选择第一个、最后一个或中间元素）
- 分区：将数组分为两部分，小于基准的元素在左边，大于基准的元素在右边
- 递归地对左边的子数组进行快速排序
- 递归地对右边的子数组进行快速排序
- 当子数组的大小为0或1时，递归结束
时间复杂度
- 最坏情况：O(n²) - 当基准选择不当，导致分区极度不平衡时
- 平均情况：O(n log n)
- 最好情况：O(n log n) - 当每次分区都能均匀分割数组时
空间复杂度
O(log n) - 快速排序需要递归调用栈的空间，平均情况下为 O(log n)。
稳定性
快速排序是不稳定的排序算法，相等元素的相对顺序可能会改变。
适用场景
- 大规模数据的排序
- 对平均性能要求高的场景
- 内存受限的环境（原地排序）
优化建议
- 使用三数取中法选择基准，避免最坏情况
- 对小规模子数组使用插入排序，减少递归开销
- 使用尾递归优化，减少栈空间使用