快速排序的核心思想与分治策略
分治理念与分区作用
快速排序基于分治思想，将一个大问题分解成更小的子问题来求解。其核心在于通过一个分区算法，把数组划分为两个区间：一侧的元素都小于等于枢轴，另一侧的元素都大于枢轴。通过这样的分区，原问题逐步转化为更小的排序问题，最终实现就地排序。本文以
在分区完成后，接着对左右子区间递归执行排序，直到区间长度为 1 或 0。时间复杂度在平均情况下为 O(n log n)，但在最坏的情况下可能退化为 O(n^2)。通过合理选择枢轴与分区策略，可以显著降低最坏情况的发生概率。
时间复杂度与稳定性简析
快速排序不是稳定排序，相等元素的相对顺序可能改变，这在某些场景需要额外处理。 稳定性并非快速排序的天然优势，若业务需要可在后续设计阶段通过特定实现变体来增强。
与其他排序算法相比，快速排序通常具有就地排序能力和较低的常数因子，这使得它在大规模数据排序中表现突出。本文的手写实现重点在于清晰呈现分区与递归的结构，便于读者理解原理与落地实现。
常见分区策略对比与选择
Lomuto 分区简介
Lomuto 分区是一种直观易懂的分区实现，通常将数组末元素作为枢轴，通过一个指针来聚集小于等于枢轴的元素，并在循环结束后将枢轴放置到正确位置。该方法代码量较少，适合初学者的手写练习。
在 Lomuto 分区中，交换操作与指针移动构成分区的核心过程，直观体现了就地排序的特性。不过在某些数据分布下，交换次数可能偏多，影响性能。
Hoare 分区简介
Hoare 分区采用双指针的双向扫描策略，通常以一个较为中性的枢轴（如中值或任意元素）进行划分，往往比 Lomuto 的交换次数更少，因此在多数场景下性能更优。
实现时需要谨慎处理边界与递归区间，分区点并不直接等同于枢轴最终位置，这会影响后续的递归区间设置。理解这一点是掌握Hoare分区的关键。
手写实现示例：基于 Lomuto 分区的快速排序
核心函数：partition 与 quicksort
以下代码给出一个简洁清晰的手写风格 C++ 实现，在原数组上就地排序，不依赖额外容器，便于直接移植到工程中。
partition 的职责是将数组分成两段：小于等于枢轴的一段与大于枢轴的一段，并返回分区点的位置。
#include <algorithm>// 快速排序（ Lomuto 分区）手写实现（就地）
void quicksort_lomuto(int arr[], int left, int right) {if (left >= right) return;int pivot = arr[right]; // 枢轴int i = left; // 小于等于 pivot 的区域边界for (int j = left; j < right; ++j) {if (arr[j] <= pivot) {std::swap(arr[i], arr[j]);++i;}}std::swap(arr[i], arr[right]);quicksort_lomuto(arr, left, i - 1);quicksort_lomuto(arr, i + 1, right);
}
这段实现展示了就地排序、简洁分区与递归调用的基本结构。若要对 C++ 的向量版本使用，可将参数改为指针与大小，保持同样的逻辑。
运行示例与边界处理
在实际调用时，应传入有效的区间 [left, right]，并确保初始调用覆盖整个数组。对于空数组或单元素数组，函数会自动跳过。 边界检查在真实项目中至关重要，能避免越界与栈溢出风险。
手写实现示例：基于 Hoare 分区的快速排序
核心逻辑对比
Hoare 分区通过双指针的对撞扫描实现，通常选择中值作为枢轴，分区后左右两部分分别进入递归。相较于 Lomuto，分区阶段的交换次数更少，在处理大规模数据时通常更高效。
需要注意的是：返回的分区下标并非枢轴的最终确定位，因此需要在递归时正确划分区间范围。
// 快速排序（ Hoare 分区）手写实现（就地）
int hoare_partition(int arr[], int left, int right) {int pivot = arr[(left + right) / 2];int i = left - 1;int j = right + 1;while (true) {do { ++i; } while (arr[i] < pivot);do { --j; } while (arr[j] > pivot);if (i >= j) return j;std::swap(arr[i], arr[j]);}
}
void quicksort_hoare(int arr[], int left, int right) {if (left < right) {int p = hoare_partition(arr, left, right);quicksort_hoare(arr, left, p);quicksort_hoare(arr, p + 1, right);}
}
这段实现展示了中位枢轴选择与双向扫描的典型写法。实际应用中可结合数据分布选择合适的枢轴策略，以降低最坏情况的可能性。
模板化与实战要点
模板化泛型实现
为了在不同数据类型间复用排序逻辑，常将快速排序设计为模板形式，并支持自定义比较器。通过模板参数与自定义比较函数，可以在 C++ 项目中广泛应用于各种容器与类型。
下面提供一个简化的模板版本示例，演示如何接入比较器而非硬编码的运算符定义。
template<typename T, typename Compare = std::less<T>>
int partition_template(T arr[], int left, int right, Compare comp = Compare()) {T pivot = arr[right];int i = left;for (int j = left; j < right; ++j) {if (comp(arr[j], pivot) || (!comp(pivot, arr[j]) && !comp(arr[j], pivot))) {std::swap(arr[i], arr[j]);++i;}}std::swap(arr[i], arr[right]);return i;
}template<typename T, typename Compare = std::less<T>>
void quicksort_template(T arr[], int left, int right, Compare comp = Compare()) {if (left < right) {int p = partition_template(arr, left, right, comp);quicksort_template(arr, left, p - 1, comp);quicksort_template(arr, p + 1, right, comp);}
}
模板化设计提升了算法的通用性与可组合性，方便与 STL 容器在实际工程中对接与复用。
边界情况与鲁棒性
在真实工程场景中，需要考虑重复元素、极端分布、以及大规模输入等情况，因此手写实现应具备容错能力。通过明确的区间检查、避免越界及合适的递归深度控制，可以提升鲁棒性。
快速排序的调优与测试
随机化枢轴与避免最坏情况
为降低最坏情况出现概率，可以在分区时采用随机化枢轴，或在 Hoare 分区中选取中位近似值作为枢轴。这样有助于让平均时间复杂度更接近 O(n log n)。
测试阶段应覆盖多种边界场景，如空数组、单元素数组、重复元素、已排序数组、反向排序数组，以确保实现的正确性与鲁棒性。
性能测试要点
在实际性能评估中，关注比较次数、交换次数、递归层数等指标，并对比 Lomuto 与 Hoare 两种分区实现的差异，帮助优化选择更合适的分区策略。
在实际项目中的应用示例
面向对象封装、模板版快速排序
在大型工程中，快速排序通常会被封装为一个可复用的模块，可以通过模板与仿函数来实现对多种数据类型的支持。通过接口设计与文档注释，可以提升代码的可读性与可维护性。
结合具体项目的数据结构，如 向量、数组、以及自定义区间类，将手写快速排序整合到排序工具库中，能带来显著的性能收益与更高的灵活性。
