快速排序通过分治法将数组按基准值划分为左右两部分并递归排序。采用双指针分区，左指针找大于等于基准的元素，右指针找小于基准的元素并交换，最终将基准置于正确位置。递归调用处理左右子区间，终止条件为子数组长度小于等于1。代码需注意下标边界，避免越界或无限递归。使用首元素作基准时，最坏情况时间复杂度为O(n²)，可通过随机选基准或三数取中优化。实际开发推荐使用std::sort。
快速排序是一种高效的排序算法，采用分治思想，通过一趟排序将数组分割成两部分，使得左边元素小于基准值，右边元素大于等于基准值，然后递归处理左右子数组。C++ 中实现快排有助于理解指针操作和递归逻辑。
基本思路与分区（Partition）
选择一个基准元素（pivot），通常取数组第一个或最后一个元素。遍历数组，将小于基准的移到左边，大于的移到右边，最终确定基准的正确位置。
示例代码中使用首元素作为基准，双指针从两端向中间扫描：- 左指针找大于等于基准的元素
- 右指针找小于基准的元素
- 交换两者，直到指针相遇
- 将基准放到正确位置
关键点： 分区过程决定算法效率，好的分区使左右子数组尽量均衡。
递归实现快排
在完成一次分区后，递归对左右两个子数组调用快排函数。递归终止条件是子数组长度小于等于1。
代码结构清晰，便于理解和调试：- 定义 partition 函数完成分区操作
- quicksort 函数调用 partition 并递归处理左右区间
- 主函数中传入数组起始和结束下标
注意： 数组下标边界处理要准确，避免越界或无限递归。
C++ 完整代码示例
以下是一个简洁可运行的 C++ 快排实现：
#includeusing namespace std; int partition(int arr[], int low, int high) { int pivot = arr[low]; int i = low + 1; int j = high;
while (true) { while (i <= j && arr[i] < pivot) i++; while (i <= j && arr[j] >= pivot) j--; if (i <= j) { swap(arr[i], arr[j]); } else { break; } } swap(arr[low], arr[j]); return j;}
void quicksort(int arr[], int low, int high) { if (low
// 打印数组 void printArray(int arr[], int size) { for (int i = 0; i
使用方式： 在 main 函数中初始化数组并调用 quicksort(arr, 0, n-1) 即可完成排序。
优化与注意事项
基础版本在有序或近似有序数据上性能较差，可能退化为 O(n²)。可通过以下方式优化：
- 随机选取基准元素
- 三数取中法选择 pivo
t
- 小数组改用插入排序
- 尾递归优化减少栈深度
提醒： 手写快排常用于面试或学习场景，实际开发推荐使用 std::sort，其内部结合了快排、堆排和插排，更稳定高效。
基本上就这些，掌握分区逻辑和递归结构是核心。不复杂但容易忽略边界细节。
t
