如何用C++实现快速排序算法？C++分治算法思想与实践【算法教程】

快速排序核心是分治：选基准将数组分为小于、等于、大于三部分，递归处理左右；需避免最坏O(n²)，推荐随机选或三数取中选基准，并用Lomuto/Hoare双指针原地分区。

快速排序用C++实现，核心是分治：选一个基准（pivot），把数组分成三部分——小于、等于、大于基准的元素，再递归处理左右两部分。关键不在“快”，而在“分得清、治得稳”。

选好基准，别硬挑第一个

基准选得太偏（比如总选首尾），最坏情况会退化成O(n²)。实际中常用三种策略：

• 随机选：用rand() % (right - left + 1) + left取下标，再和末尾交换
• 三数取中：取首、中、尾三个数的中位数作基准，抗有序/逆序数据效果好
• 避免重复拷贝：直接在原数组上分区，不用额外容器存“等于”部分

双指针分区，原地完成

推荐Lomuto或Hoare分区方案。Lomuto更易懂，用一个游标i标记“

• 遍历j从left到right−1，遇到≤pivot的数，就swap(arr[++i], arr[j])
• 最后swap(arr[i+1], arr[right])，把pivot放到正确位置
• 返回i+1，即pivot最终下标，左右子数组就是[left, i]和[i+2, right]

递归控制，别忘剪枝

小数组用插入排序更高效（一般n ≤ 10就切换），避免深层递归开销：

标签： c++ 排序算法