快速排序

定义

快速排序是一种采用分治思想的高效排序算法。它选取一个基准元素（pivot），将序列划分为小于基准和大于基准两部分，再对两部分递归排序。

原理

核心是划分操作：选定基准后，通过双指针扫描把比基准小的放左边、大的放右边，使基准落到最终位置。然后对左右子区间分别递归。基准选择会影响性能，若每次都选到最大或最小值会退化；常用随机选取或三数取中来避免。快速排序是原地排序，但不稳定。

复杂度

• 时间复杂度（平均）：O(n log n)
• 时间复杂度（最坏，划分极不均）：O(n²)
• 空间复杂度（递归栈）：O(log n)
• 稳定性：不稳定

应用场景

• 通用大规模内存排序（多数语言库的默认实现之一）
• 快速选择求第 K 大
• 对平均性能要求高的场景