快速排序采用分治策略，通过分区操作将数组分为两部分并递归排序。选择基准元素后，用双指针法重排数组，使左侧元素小于等于基准，右侧大于基准，基准置于正确位置。常用Lomuto分区方案以末尾元素为基准，通过交换实现分区，返回基准位置供递归使用。完整代码包含partition和quickSort函数，主函数演示了排序过程。优化方法包括随机化基准、三数取中、小数组改用插入排序及尾递归优化，提升性能与稳定性。C++标准库的std::sort结合快排、堆排和插排，适应多种数据场景。
快速排序是一种高效的排序算法，采用分治策略来把一个序列分成两个子序列。它的平均时间复杂度为 O(n log n)，在实际应用中表现优秀，是 C++ 中常用的排序方法之一。下面详细介绍快速排序的实现原理和完整代码。
快速排序的基本思想
快速排序的核心是“分区”（partition）操作。从数组中选择一个基准元素（pivot），然后将数组中小于基准的元素移到左边，大于基准的元素移到右边，基准放在中间。这个过程完成后，基准元素的位置就是它在最终有序数组中的位置。接着对左右两个子数组递归执行相同的操作。
关键步骤包括：
- 选择一个基准值（通常选首元素、尾元素或中间元素）
- 重新排列数组，使小于基准的在左，大于的在右
- 递归地对左右子数组进行快排
分区操作的实现方式
常见的分区方法是使用双指针法。以下是以最后一个元素为基准的 Lomuto 分区方案：
立即学习“C++免费学习笔记（深入）”；
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 基准
int i = low - 1; // 小于基准区域的边界
<pre class='brush:php;toolbar:false;'>for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;}
该函数返回基准元素的最终位置，便于后续递归调用划分区间。
完整的快速排序代码
结合递归函数，可以写出完整的快速排序实现：
#include <iostream>
<p>void quickSort(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);
}
}</p><p>// 使用示例
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);</p><pre class='brush:php;toolbar:false;'>quickSort(arr, 0, n - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < n; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
return 0;}
优化建议与注意事项
虽然基础版本已经有效，但可以通过一些技巧提升性能：
- 随机化基准：避免最坏情况（如已排序数组），可随机选择 pivot 并与末尾交换
- 三数取中法：取首、中、尾三个元素的中位数作为基准
- 小数组改用插入排序：当子数组长度小于 10 左右时切换为插入排序更高效
- 尾递归优化：先处理较小区间，减少栈深度
基本上就这些。快速排序理解起来不难，但细节决定效率。掌握好分区逻辑和边界控制，就能写出稳定高效的版本。C++ 标准库中的 std::sort 实际上结合了快排、堆排序和插入排序（Introsort），以应对各种数据场景。
