c++分治法快速排序

在C++中，分治法是一种常用的算法设计策略，特别是用于排序算法如快速排序（QuickSort）。快速排序的核心思想是将一个大问题分解成两个小问题，然后递归地解决这些小问题，最后合并结果。

以下是快速排序的基本步骤：

1. **选择基准**（pivot）：通常选择数组的第一个元素作为基准，也可以随机选取。

2. **分区操作**（Partition）：将数组分为两部分，一部分的所有元素都小于基准，另一部分所有元素都大于或等于基准。这个过程通过一趟从左到右的扫描完成，遇到比基准大的元素就交换它到右侧，遇到比基准小的元素保持不变。

3. **递归排序**：对左右两个分区分别进行上述的快速排序步骤，直到每个分区只剩下一个元素或为空。

4. **合并结果**：当所有子数组都排好序后，原始数组也就被排好了。

C++中的快速排序代码示例如下：

#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 pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);