快速排序的核心思想
快速排序的核心思想是分治法：选一个元素作为基准，将数组分成两部分，使得左边所有元素 ≤ 基准，右边所有元素 ≥ 基准。然后对左右两部分递归执行同样的操作。这就像整理书架：先挑一本书作为标准，把比它矮的放左边，比它高的放右边，再分别整理左右两堆。
分区 partition 怎么做
分区是快速排序的关键步骤。通常用两个指针从数组两端向中间扫描：左指针找比基准大的元素，右指针找比基准小的元素，找到后交换它们，直到两指针相遇。最后将基准放到正确位置。这样一次分区就确定了基准的最终位置，且左边都不大于它，右边都不小于它。
递归处理左右两半
分区后，基准已经就位，左右两半是独立的子问题。对左半部分和右半部分分别递归调用快速排序。递归的终止条件是子数组长度 ≤ 1（已经有序）。由于每次分区都固定一个元素的位置，递归深度就是调用栈的层数。
平均 O(n log n) 与最坏 O(n²)
| 情况 | 时间复杂度 | 原因 |
|---|---|---|
| 平均 | O(n log n) | 每次分区大致均匀，递归深度 log n，每层总比较次数 O(n) |
| 最坏 | O(n²) | 每次分区极不平衡（如数组已有序且基准选最左/最右），递归深度 n |
最坏情况发生在基准总是最大或最小元素，导致分区后一边为空。实际中通过随机化基准可以大大降低最坏概率。
基准选择与优化（随机基准/三数取中）
为避免最坏情况，常用随机基准：随机选一个元素作为基准，使输入顺序的影响最小化。另一种常用优化是三数取中：取左端、中间、右端三个元素的中位数作为基准，这样分区更均衡。这些方法让快速排序在实际中几乎总是 O(n log n)。