快速排序核心思想
快速排序的核心在于分治策略。简单来说，就是'分而治之'。它通过三个步骤实现高效排序：
- 选基准：从待排序数组中选择一个元素作为「基准值」（pivot）。
- 分区操作：遍历数组，将小于基准值的元素放到左侧，大于基准值的放到右侧。这一步结束后，基准值会被放到最终排序的正确位置。
- 递归排序子区间：对基准值左右两侧的子数组，重复上述步骤，直到子数组长度为 0 或 1。
这种'拆分为小问题→独立解决→自然合并'的思路，避免了归并排序的额外合并开销，是快排高效的根源。
Hoare 分区方案
Hoare 版本是经典的原地分区实现，由算法发明者 Tony Hoare 提出，核心是双指针相向遍历。
核心逻辑： 针对升序排序，选取区间首元素为基准值 key。右指针从后向前找首个小于 key 的元素，左指针再从前向后找首个大于 key 的元素，交换两者并重复，直到相遇。最后将基准值与相遇位置交换。需注意遵循「右指针先行」规则，否则会导致基准归位错误。
代码实现：
void QuickSort1(int* a, int left, int right) {
if (left >= right) return;
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);
}
这里有个细节：当 left 和 right 指定的数据和 key 值相等时不能直接交换，否则可能陷入死循环或逻辑错误，需确保指针移动越过相同值。
常见优化策略
1. 有序情况优化
如果数组本身有序，每次选最左/最右元素会导致递归树退化成链表，时间复杂度变为 O(n²)。我们可以通过以下方法避免：
随机选基准：
int randi = left + rand() % (right - left + 1);
swap(&a[randi], &a[keyi]);
即使输入有序，随机选也能大概率让递归树保持平衡，将最坏情况优化为概率上的 O(nlogn)。
三数取中： 从区间左、中、右三个位置选出数值居中的元素作为基准，进一步降低极端情况出现的概率。
int {
midi = (right + left) / ;
mid_index;
}
