C++实现快速排序算法

快速排序是一种高效的排序算法，采用分治策略，平均时间复杂度为O(n*logn)。本文将介绍如何使用C++实现快速排序算法。

算法原理

快速排序包括以下步骤：

1. 选择基准值（pivot）
2. 将数据分为两部分：小于等于基准值的部分和大于基准值的部分
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 - 1; 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 pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    vector<int> arr = {10, 80, 30, 90, 40, 50, 70};
    int n = arr.size();

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

总结

我们在这篇文章中，介绍了快速排序算法的原理，并给出了C++的实现。作为一种高效排序算法，快速排序在许多场景下都非常实用。希望您能从这篇文章中受益。