快速排序核心是分治：选基准将数组分为小于、等于、大于三部分，递归处理左右；需避免最坏O(n²)，推荐随机选或三数取中选基准，并用Lomuto/Hoare双指针原地分区。
快速排序用C++实现，核心是分治：选一个基准（pivot），把数组分成三部分——小于、等于、大于基准的元素，再递归处理左右两部分。关键不在“快”，而在“分得清、治得稳”。
基准选得太偏（比如总选首尾），最坏情况会退化成O(n²)。实际中常用三种策略：
推荐Lomuto或Hoare分区方案。Lomuto更易懂，用一个游标i标记“
小数组用插入排序更高效（一般n ≤ 10就切换），避免深层递归开销：
立即学习“C++免费学习笔记（深入）”；
以下代码含随机基准 + Lomuto分区 + 小数组优化：
void quick_sort(vector<int>& arr, int left = 0, int right = -1) {
if (right == -1) right = arr.size() - 1;
if (left >= right) return;
if (right - left <= 10) {
insertion_sort(arr, left, right);
return;
}
// 随机选基准并换到末尾
int rnd = left + rand() % (right - left + 1);
swap(arr[rnd], arr[right]);
int pivot_idx = partition(arr, left, right);
quick_sort(arr, left, pivot_idx - 1);
quick_sort(arr, pivot_idx + 1, right);
}
<p>int partition(vector<int>& arr, int left, int right) {
int pivot = arr[right], i = left - 1;
for (int j = left; j < right; ++j) {
if (arr[j] <= pivot) swap(arr[++i], arr[j]);
}
swap(arr[i + 1], arr[right]);
return i + 1;
}
基本上就这些。分治不是玄学，是“先想清楚怎么拆，再放心交给自己去算”。写快排时多调试几个边界案例（全等、已序、逆序、两个数），比背模板管用得多。
以上就是如何用C++实现快速排序算法？C++分治算法思想与实践【算法教程】的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
386
收藏
