如何用c++实现快速排序算法经典排序算法代码实现【算法教程】_网络技术

发布时间 - 2026-01-09 00:00:00 点击率：次

快速排序核心是分治：选基准将数组分为小于、等于、大于三部分，再递归处理前后两部分；C++实现需注意边界控制、原地排序、三路优化及基准随机化等细节。

快速排序的核心是“分治”：选一个基准元素，把数组分成三部分——小于基准的、等于基准的、大于基准的，再递归处理前后两部分。C++实现时要注意边界控制和原地排序优化，避免额外空间开销。

这是最易理解的写法，用一个基准值（通常取末尾元素），维护一个慢指针 i 指向已处理中小于等于基准的区域右边界，快指针 j 遍历整个待排段。

关键步骤：

当数组中存在大量重复值时，标准快排可能退化为 O(n²)。三路快排把区间划分为 、== pivot、> pivot 三段，跳过所有等于基准的元素，大幅提升稳定性。

立即学习“C++免费学习笔记（深入）”；

实现要点：

用两个指针 lt（less than）和 gt（greater than），初始分别指向 l 和 r
用游标 i 从左往右扫描：
  – 若 arr[i] ，交换 arr[i] 与 arr[++lt]；
  – 若 arr[i] > pivot，交换 arr[i] 与 arr[--gt]，且 i 不增（因右边换来的数未检查）；
  – 若相等，i++ 跳过

写快排容易出错的地方集中在递归边界和分区逻辑上：

递归调用时，左右子区间必须严格不重叠，比如分区后基准在 pos，则递归范围应为 [l, pos−1] 和 [pos+1, r]，不能写成 [l, pos]
小数组改用插入排序（例如长度 ≤10），减少递归开销
基准选取建议随机化：用 swap(arr[l], arr[l + rand() % (r−l+1)]) 防止有序数组最坏情况
C++ 中注意使用引用传参（vector&）避免拷贝，提升效率

快排不是黑盒，理解分区过程比背代码更重要。动手写一遍 Lomuto 版本，再改成三路，你会明显感受到“划分”这个动作如何驱动整个排序流程。不复杂但容易忽略细节。