C++ 快速排序算法实现_C++经典排序算法手写代码

快速排序通过分治法将数组按基准值划分为左右两部分并递归排序。采用双指针分区，左指针找大于等于基准的元素，右指针找小于基准的元素并交换，最终将基准置于正确位置。递归调用处理左右子区间，终止条件为子数组长度小于等于1。代码需注意下标边界，避免越界或无限递归。使用首元素作基准时，最坏情况时间复杂度为O(n²)，可通过随机选基准或三数取中优化。实际开发推荐使用std::sort。

快速排序是一种高效的排序算法，采用分治思想，通过一趟排序将数组分割成两部分，使得左边元素小于基准值，右边元素大于等于基准值，然后递归处理左右子数组。C++ 中实现快排有助于理解指针操作和递归逻辑。

基本思路与分区（Partition）

选择一个基准元素（pivot），通常取数组第一个或最后一个元素。遍历数组，将小于基准的移到左边，大于的移到右边，最终确定基准的正确位置。

• 左指针找大于等于基准的元素
• 右指针找小于基准的元素
• 交换两者，直到指针相遇
• 将基准放到正确位置

关键点： 分区过程决定算法效率，好的分区使左右子数组尽量均衡。

递归实现快排

在完成一次分区后，递归对左右两个子数组调用快排函数。递归终止条件是子数组长度小于等于1。

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

• 定义 partition 函数完成分区操作
• quicksort 函数调用 partition 并递归处理左右区间
• 主函数中传入数组起始和结束下标

注意： 数组下标边界处理要准确，避免越界或无限递归。

C++ 完整代码示例

以下是一个简洁可运行的 C++ 快排实现：

百灵大模型

蚂蚁集团自研的多模态AI大模型系列

313

查看详情

#include <iostream>
using namespace std;
<p>int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low + 1;
int j = high;</p><pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">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 < high) { int pi = partition(arr, low, high); quicksort(arr, low, pi - 1); quicksort(arr, pi + 1, high); } }

// 打印数组 void printArray(int arr[], int size) { for (int i = 0; i < size; ++i) cout << arr[i] << " "; cout << endl; }

使用方式： 在 main 函数中初始化数组并调用 quicksort(arr, 0, n-1) 即可完成排序。

优化与注意事项

基础版本在有序或近似有序数据上性能较差，可能退化为 O(n²)。可通过以下方式优化：

• 随机选取基准元素
• 三数取中法选择 pivot
• 小数组改用插入排序
• 尾递归优化减少栈深度

提醒： 手写快排常用于面试或学习场景，实际开发推荐使用 std::sort，其内部结合了快排、堆排和插排，更稳定高效。

基本上就这些，掌握分区逻辑和递归结构是核心。不复杂但容易忽略边界细节。

以上就是C++ 快速排序算法实现_C++经典排序算法手写代码的详细内容，更多请关注php中文网其它相关文章！