快速排序核心原理
快速排序的核心思想是分治策略，简单来说就是'分而治之'。它通过三步实现高效排序：
- 选基准：从待排序数组中选择一个元素作为「基准值」（pivot）。
- 分区操作：遍历数组，将小于基准值的元素放到基准值左侧，大于基准值的元素放到右侧。这一步结束后，基准值会被放到最终排序的正确位置。
- 递归排序子区间：对基准值左侧和右侧的两个子数组，重复执行上述步骤，直到所有子数组的长度为 0 或 1。
这种'拆分为小问题→独立解决→自然合并'的思路，是分治思想的典型体现。其高效性正是源于「分区」这一步：它通过一次遍历就将一个大问题拆分成了两个规模更小的子问题。
Hoare 版本
Hoare 版本是快速排序的经典原地分区实现，由算法发明者 Tony Hoare 提出，核心是双指针相向遍历。
针对升序排序，首先选取区间首元素作为基准值 key，然后右指针从右向左寻找首个小于 key 的元素，左指针再从左向右寻找首个大于 key 的元素，交换两指针指向的元素并重复此过程，直到两指针相遇。最后将基准值与相遇位置的元素交换，即可完成分区。
需要注意的是，必须遵循「右指针先行」规则，否则会导致基准归位错误。当 left 和 right 指定的数据和 key 值相等时，不能直接交换，否则可能陷入死循环或逻辑错误。
void QuickSort1(int* a, int left, int right) {
if (left >= right) {
return;
}
// 初始化指针：begin/end 遍历区间，keyi 标记基准值初始位置（选左端点为基准）
int begin = left;
int end = right;
int keyi = left;
// 双指针相向遍历，完成区间分区
while (begin < end) {
// 右指针从后往前找：第一个比基准值小的元素
while (begin < end && a[end] >= a[keyi]) {
end--;
}
// 左指针从前往后找：第一个比基准值大的元素
while (begin < end && a[begin] <= a[keyi]) {
begin++;
}
// 交换找到的两个元素，让小值到左、大值到右
swap(&a[begin], &a[end]);
}
// 指针相遇时，该位置就是基准值的最终位置，交换归位
swap(&a[keyi], &a[begin]);
keyi = begin;
// 递归处理基准值左右两侧的子区间
QuickSort1(a, left, keyi - 1);
QuickSort1(a, keyi + 1, right);
}
时间复杂度分析
在最优情况下，每次划分都能将数组均匀分成两部分，递归树会有 logN 层，且每一层都需要处理约 N 个元素，总的时间复杂度为 O(NlogN)。
如果数组是有序的情况，无法达到均分，最坏时间复杂度会退化为 O(n²)。但在实际工程中，我们会对快排进行优化，让其能近似达到一个平衡二叉树的状态。
