实现快速排序问题C++

快速排序是一种常用的排序算法，基于分治策略。它的基本思想是选择一个基准值，将数组分成两个部分，一部分的所有元素都小于基准，另一部分的所有元素都大于基准，然后对这两部分分别进行快速排序。下面是C++实现快速排序的基本步骤：

#include <iostream>
#include <vector>

// 交换两个元素的位置
template<typename T>
void swap(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

// 选择基准并分区
template<typename T>
void partition(std::vector<T>& arr, int low, int high) {
    T 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]); // 将基准放到正确位置
}

// 快速排序函数
template<typename T>
void quickSort(std::vector<T>& 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() {
    std::vector<int> numbers = {9, 7, 5, 11, 12, 2, 14, 3, 10};
    int n = numbers.size();
    quickSort(numbers, 0, n - 1);
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

在这个例子中，我们首先定义了一个`quickSort`函数，然后在`main`函数中创建了一个整数向量并对其进行排序。