C++实现快速排序（入门级详解）
 
快速排序是算法学习中最经典的排序算法之一，凭借分治思想和优秀的平均时间复杂度，成为实际开发中常用的排序方法。今天就用C++从零实现快速排序，用最简单的方式讲清核心思路，适合刚接触算法的计算机专业同学学习。
 
一、快速排序的核心思想
 
快速排序的核心是分治+基准值划分：
 
1. 选基准：从数组中选一个元素作为基准值（pivot），通常选数组中间元素或首尾元素；
2. 分区：遍历数组，将小于基准值的元素放到基准左侧，大于基准值的放到右侧，基准值最终处于正确位置；
3. 递归：对基准值左侧和右侧的子数组，重复上述步骤，直到子数组长度为1（天然有序）。
 
快速排序的平均时间复杂度为O(n\log n)，最坏时间复杂度为O(n^2)（极端有序数组），空间复杂度为O(\log n)（递归调用栈）。
 
二、C++代码实现
 
cpp
  
#include <iostream>
#include <vector>
using namespace std;

// 分区函数：返回基准值的最终位置
int partition(vector<int>& nums, int left, int right) {
    // 选最右侧元素作为基准值
    int pivot = nums[right];
    // i是小于基准值区域的右边界
    int i = left - 1;
    for (int j = left; j < right; j++) {
        // 若当前元素小于等于基准值，划入左侧区域
        if (nums[j] <= pivot) {
            i++;
            swap(nums[i[j nums[j]);
        }
    }
    // 将基准值放到正确位置（i+1）
    swap(nums[i+1], nums[right]);
    return i + 1;
}

// 快速排序递归函数
void quickSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        // 获取基准值位置
        int pivotIndex = partition(nums, left, right);
        // 递归排序左子数组
        quickSort(nums, left, pivotIndex - 1);
        // 递归排序右子数组
        quickSort(nums, pivotIndex + 1, right);
    }
}

// 测试示例
int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    cout << "排序前：";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    quickSort(nums, 0, nums.size() - 1);

    cout << "排序后：";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}
 
 
三、代码解释
 
1. partition函数：负责将数组按基准值分区，返回基准值的最终索引。通过遍历数组，把小于等于基准值的元素交换到左侧，最后将基准值放到左右区域的中间。
2. quickSort函数：递归处理基准值左右的子数组，直到子数组无法再分割（left >= right）。
3. 主函数：定义测试数组，调用快速排序并输出排序前后的结果，直观验证效果。
 
四、入门小技巧
 
1. 基准值选择：入门阶段选数组末尾元素即可，进阶可采用“三数取中法”（选首、中、尾元素的中位数），避免最坏情况；
2. 边界处理：递归时注意 pivotIndex - 1 和 pivotIndex + 1 ，不要包含基准值本身；
3. 小数组优化：当子数组长度小于10时，可改用插入排序，减少递归开销。
 
如果这篇文章对你理解快速排序有帮助，欢迎点赞、收藏、关注～有其他排序算法的疑问，也可以在评论区留言交流！
 
 
 
要不要我帮你补充快速排序的优化版本（三数取中法）和时间复杂度的详细推导，让内容更深入？