C++怎么实现一个快速排序算法

快速排序是一种采用分治思想的经典排序算法，核心逻辑是通过选取基准元素将待排序序列划分为两部分，左侧元素均小于等于基准，右侧元素均大于基准，再对两部分分别递归排序，最终得到有序序列。

快速排序核心原理

快速排序的执行过程可以分为三个关键步骤：

• 选取基准：从待排序序列中挑选一个元素作为基准，通常可以选择序列的第一个、最后一个或者中间的元素。
• 分区操作：遍历整个序列，将小于等于基准的元素移到基准左侧，大于基准的元素移到基准右侧，最终基准元素会处于其最终排序位置。
• 递归排序：对基准左侧和右侧的两个子序列分别重复上述选取基准、分区、递归的过程，直到子序列长度小于等于1，排序完成。

完整C++实现代码

以下是基于递归实现的快速排序完整代码，包含分区函数和排序入口函数：

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

// 分区函数，返回基准元素的最终位置
int partition(vector<int>& arr, int left, int right) {
    // 选取最右侧元素作为基准
    int pivot = arr[right];
    // i指向小于等于基准区域的最后一个位置
    int i = left - 1;
    for (int j = left; j < right; j++) {
        // 如果当前元素小于等于基准，将其交换到左侧区域
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    // 将基准元素放到最终正确位置
    swap(arr[i + 1], arr[right]);
    return i + 1;
}

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

// 打印数组的辅助函数
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> testArr = {10, 7, 8, 9, 1, 5};
    cout << "排序前的数组：";
    printArray(testArr);
    
    quickSort(testArr, 0, testArr.size() - 1);
    
    cout << "排序后的数组：";
    printArray(testArr);
    return 0;
}

代码执行流程说明

以测试用例vector<int> testArr = {10, 7, 8, 9, 1, 5}为例，排序过程如下：

1. 第一次选取基准为5，分区后数组变为{1, 7, 8, 9, 10, 5}，基准5移动到索引1的位置，左侧子序列为{1}，右侧子序列为{8, 9, 10, 7}。
2. 对右侧子序列{8, 9, 10, 7}选取基准7，分区后变为{7, 9, 10, 8}，基准7到索引1位置，右侧子序列为{9, 10, 8}。
3. 继续对{9, 10, 8}排序，最终整个数组变为{1, 5, 7, 8, 9, 10}，排序完成。

快速排序特性分析

优化建议

为了避免最坏时间复杂度的出现，可以对基准选取方式做优化：

• 三数取中法：选取序列左端、中间、右端三个元素的中值作为基准，减少有序序列下的性能退化。
• 随机选取基准：每次从待排序序列中随机选择一个元素作为基准，降低最坏情况出现的概率。
• 小序列切换插入排序：当子序列长度小于某个阈值（比如10）时，改用插入排序，减少递归开销。

快速排序适合处理大规模无序数据的排序场景，在C++标准库的std::sort实现中，也结合了快速排序、堆排序、插入排序的特性，保证不同场景下的排序效率。

C++快速排序QuickSort排序算法修改时间：2026-07-18 20:09:25