快速排序算法详解 C++代码实现

一、简介和特点

快速排序（QuickSort）是一种经典的高效排序算法，采用分治思想：通过选定一个枢轴元素（pivot），将数组划分为左右两部分，使左侧元素均小于枢轴，右侧元素均大于枢轴，再递归对子数组排序。其平均时间复杂度为O(nlogn)，在大多数情况下表现优异。本文代码实现中，作者自定义了枢轴选择方法（通过idx函数），试图优化分区过程，但具体效果需结合数据分布分析。

二、与其他排序算法相比的优点

1. 高效性：平均时间复杂度优于冒泡、选择、插入排序（O(n^2)）。

2. 原地排序：仅需常数额外空间，无需大量辅助数组。

3. 递归实现：代码结构清晰，易于理解和递归逻辑的练习。

4. 适用性广：适用于大规模数据排序，实际工程中常用优化版本（如随机化枢轴、三路快排等）。

三、步骤解析

1. 枢轴选择：通过idx函数，选取数组中最大值对应的索引，再对数组长度取模作为实际枢轴值（val）。该策略意图避免直接使用最大值导致分区不平衡，但可能因取模操作引入额外计算开销。

2. 分区操作：创建左右子数组，遍历原数组，将小于val的元素放入left，大于val的元素放入right，相等元素暂不处理。

3. 递归排序：对left和right递归调用quicksort，完成后合并结果：先添加left元素，再添加枢轴val，最后添加right元素至原数组。

4. 边界处理：当数组长度小于2时，直接返回，避免递归深度过大。

四、带注释的代码

#include<iostream>
#include<vector>
using namespace std;

// 自定义枢轴选择函数：选取数组中最大值对应的索引，再对数组长度取模作为枢轴值
int idx(vector<int> a) {
    int maxv = 0; // 初始化最大值
    for (int i = 0; i < a.size(); i++) // 遍历数组
        maxv = max(maxv, a[i]); // 更新最大值
    return a[maxv % a.size()]; // 返回最大值索引对数组长度取模后的元素值
}

// 快速排序主函数
void quicksort(vector<int>& a) {
    if (a.size() < 2) return; // 递归终止条件：数组长度小于2时直接返回

    int val = idx(a); // 获取枢轴值
    vector<int> left; // 左侧子数组
    vector<int> right; // 右侧子数组

    for (int i = 0; i < a.size(); i++) { // 遍历原数组进行分区
        if (a[i] < val) // 小于枢轴，加入左侧
            left.push_back(a[i]);
        else if (a[i] > val) // 大于枢轴，加入右侧
            right.push_back(a[i]);
        // 注意：相等元素未处理，可能导致分区不严格，但此处为简化实现
    }

    quicksort(left); // 递归排序左侧子数组
    quicksort(right); // 递归排序右侧子数组

    a.clear(); // 清空原数组（为后续合并腾空间）
    for (int i = 0; i < left.size(); i++) a.push_back(left[i]); // 合并左侧元素
    a.push_back(val); // 添加枢轴值
    for (int i = 0; i < right.size(); i++) a.push_back(right[i]); // 合并右侧元素
}

五、总结

本文手搓的快速排序实现通过自定义枢轴选择策略尝试优化传统算法，但实际性能取决于数据分布。算法核心在于递归分区与合并，适合作为学习分治思想的入门案例。