快速排序采用分治法，通过选取基准分区实现高效排序。1. 分解：选基准（如首元素），用双指针将小于基准的放左，大于的放右；2. 解决：递归对左右子数组排序；3. 合并：无需显式合并，划分后基准已就位。常用Lomuto分区法，以首元素为pivot，遍历并交换元素，最后将基准置于正确位置。C++实现中，partition函数返回基准索引，quickSort递归处理两侧。平均时间复杂度O(n log n)，最坏O(n²)，优化策略包括随机选基准、三数取中和小数组用插入排序。关键细节在于边界控制与基准放置，理解分区逻辑即可灵活实现。
快速排序（Quick Sort）是一种高效的排序算法，采用分治思想实现。它的核心思路是：从数组中选择一个“基准”元素，将小于基准的元素移到左边，大于基准的移到右边，然后对左右两部分递归处理，最终使整个数组有序。
分治三步走：分解、解决、合并
快速排序虽然不需要显式的“合并”步骤，但完整体现了分治法的逻辑：
- 分解：选取基准值（pivot），将数组划分为两个子数组，左半边都小于等于基准，右半边都大于基准。
- 解决：递归地对左右两个子数组进行快速排序。
- 合并：由于每轮划分后基准已处于正确位置，递归完成后数组自然有序，无需额外操作。
如何选择基准和分区？
分区（Partition）是快速排序的关键步骤。常用方法是双指针法，从数组两端向中间扫描，交换不符合条件的元素。
以下是基于首元素为基准的Lomuto分区方式简化实现（也可使用Hoare分区）：
立即学习“C++免费学习笔记（深入）”；
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[low]; // 选第一个元素为基准
int i = low + 1;
for (int j = low + 1; j <= high; j++) {
if (arr[j] < pivot) {
swap(arr[i], arr[j]);
i++;
}
}
swap(arr[low], arr[i - 1]); // 基准放到正确位置
return i - 1;
}
C++完整实现代码
结合递归调用，完成完整的快速排序函数：
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 获取基准索引
quickSort(arr, low, pi - 1); // 排左半部分
quickSort(arr, pi + 1, high); // 排右半部分
}
}
调用示例：
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr, 0, arr.size() - 1);
// 输出结果：11 12 22 25 34 64 90
性能分析与优化建议
快速排序平均时间复杂度为O(n log n)，最坏情况为O(n²)，但实际表现通常优于其他O(n log n)算法。
- 最好情况：每次划分都能均分数组。
- 最坏情况：数组已有序，且每次都选到最小或最大元素作基准。
- 优化方式：随机选取基准、三数取中法、小数组改用插入排序等。
基本上就这些。理解分治逻辑和分区过程，就能灵活实现并优化快速排序。不复杂但容易忽略细节，比如边界控制和基准放置。
