C++快速排序算法详解（小白也能学会的分治排序教程）

快速排序的步骤

1. 选择基准：通常选择数组的第一个、最后一个或中间的元素作为基准。
2. 分区（Partition）：重新排列数组，使得所有小于基准的元素在左边，大于基准的在右边。
3. 递归排序：对左右两个子数组分别递归执行快速排序。

C++快速排序代码实现

下面是一个完整的、易于理解的 C++ 快速排序实现：

#include <iostream>#include <vector>using namespace std;// 分区函数：将数组按基准值划分int partition(vector<int>& arr, int low, int high) {    int pivot = arr[high]; // 选择最后一个元素作为基准    int i = low - 1; // 小于基准的元素的索引    for (int j = low; j < high; j++) {        if (arr[j] <= pivot) {            i++;            swap(arr[i], arr[j]);        }    }    swap(arr[i + 1], arr[high]);    return i + 1;}// 快速排序主函数void quickSort(vector<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);  // 递归排序右半部分    }}// 主函数：测试快速排序int main() {    vector<int> arr = {10, 7, 8, 9, 1, 5};    int n = arr.size();    cout << "排序前: ";    for (int x : arr) cout << x << " ";    cout << endl;    quickSort(arr, 0, n - 1);    cout << "排序后: ";    for (int x : arr) cout << x << " ";    cout << endl;    return 0;}

代码说明

• partition 函数负责将数组按基准值分割，并返回基准的最终位置。
• quickSort 是递归函数，不断对子数组进行排序。
• 主函数中我们创建了一个测试数组，并调用 quickSort 对其排序。

时间复杂度分析

- 最好情况：每次分区都能平均划分，时间复杂度为 O(n log n)。
- 最坏情况：每次选到最大或最小元素作基准，退化为 O(n²)，但可通过随机选择基准优化。
- 平均情况：O(n log n)，实际性能通常优于其他 O(n log n) 排序算法。

总结

通过本教程，你应该已经掌握了 C++快速排序 的基本原理与实现方法。它不仅是面试常考题，也是实际开发中常用的高效排序手段。记住，理解分治算法C++的思想是掌握快速排序的关键！

希望这篇 C++排序教程 对你有所帮助。动手写一写代码，你会对 快速排序算法 有更深刻的理解！