快速排序通过分治法实现高效排序，核心是选择基准并分区。1. 选末尾元素为基准，用partition函数将小于等于基准的移到左边，大于的移到右边，并返回基准正确位置；2. 递归对左右子数组调用quickSort；3. C++代码实现包括partition、quickSort和打印函数；4. 示例展示排序前后的数组变化；5. 优化建议含随机化基准、三数取中、小数组用插入排序及尾递归优化。掌握partition是关键。
快速排序是一种高效的排序算法，采用分治策略来把一个序列分成两个子序列，然后递归排序。它的平均时间复杂度为 O(n log n)，在实际应用中表现优异。
快排算法基本原理
快速排序的核心思想是选择一个“基准”（pivot），将数组中小于基准的元素移到左边，大于基准的元素移到右边，这个过程称为分区（partition）。完成分区后，基准元素的位置就是它在最终有序数组中的位置。接着对左右两个子数组递归执行相同操作。
具体步骤如下：
- 从数组中选择一个元素作为基准（通常选第一个、最后一个或中间元素）
- 重新排列数组，使所有小于基准的元素位于其左侧，大于等于的位于右侧
- 对左右两个子数组分别递归调用快排
C++代码实现
下面是一个简洁且高效的C++实现版本，使用最右边的元素作为基准：
立即学习“C++免费学习笔记（深入）”；
#include#include // 分区函数：将数组按基准划分 int partition(std::vector
& arr, int low, int high) { int pivot = arr[high]; // 以最后一个元素为基准 int i = low - 1; // 小于基准的区域的边界 for (int j = low; j zuojiankuohaophpcn high; j++) { if (arr[j] zuojiankuohaophpcn= pivot) { i++; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); // 将基准放到正确位置 return i + 1; // 返回基准的索引}
// 快速排序主函数 void quickSort(std::vector
& arr, int low, int high) { if (low quickSort(arr, low, pi - 1); // 排序基准左边 quickSort(arr, pi + 1, high); // 排序基准右边 }}
// 打印数组 void printArray(const std::vector
& arr) { for (int val : arr) std::cout 使用示例：
int main() { std::vectorarr = {10, 7, 8, 9, 1, 5}; int n = arr.size(); std::cout zuojiankuohaophpcnzuojiankuohaophpcn "排序前: "; printArray(arr); quickSort(arr, 0, n - 1); std::cout zuojiankuohaophpcnzuojiankuohaophpcn "排序后: "; printArray(arr); return 0;}
优化建议与注意事项
虽然上述实现清晰易懂，但在实际使用中可考虑以下几点优化：
- 随机化基准：避免最坏情况（如已排序数组），可随机选择基准并与其末尾元素交换
- 三数取中法：取首、中、尾三个元素的中位数作为基准
- 小数组改用插入排序：当子数组长度小于10时，插入排序更高效
- 尾递归优化：先处理较小的子数组，减少栈深度
基本上就这些。快速排序理解起来不难，关键在于分区逻辑的正确实现和递归边界的控制。写好 partition 函数，整个算法就成功了一大半。
