用cpp设计分治法实现快速排序算法。利用递归思想，实现快速排序。

在C++中，我们可以使用分治策略实现快速排序算法。快速排序是一种高效的排序算法，其基本思想是选取一个基准元素，将数组分为两部分，一部分所有元素都小于基准，另一部分所有元素都大于基准，然后对这两部分再分别进行快速排序。以下是使用递归实现的基本步骤：

#include <iostream>
using namespace std;

// 交换两个元素的位置
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分治法的核心函数：快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 选择一个基准元素（通常最后一个元素）
        int pivot = arr[high];
        
        // 定义两个指针，i指向小于基准的最右边，j指向大于基准的左边
        int i = low - 1; // 指向小于基准的前一个位置
        for (int j = low; j <= high - 1; j++) {
            // 如果当前元素小于等于基准
            if (arr[j] <= pivot) {
                i++; // 将i右移一位
                swap(&arr[i], &arr[j]); // 交换 arr[i] 和 arr[j]
            }
        }
        // 将基准元素放到正确的位置（即i+1处）
        swap(&arr[i + 1], &arr[high]);
        
        // 对左右两个子数组分别进行递归排序
        quickSort(arr, low, i); // 左半部分
        quickSort(arr, i + 2, high); // 右半部分
    }
}

// 测试函数
int main() {
    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    quickSort(arr, 0, n - 1);

    cout << "\nSorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    
    return 0;
}

在这个示例中，`quickSort`函数就是分治的核心，通过递归地调用自身，不断缩小待排序区间直到只剩下一个元素，实现了快速排序。