C++分治代码怎么写

Question

我正在学习C++算法
分治实在有点难理解
请大家帮帮忙,随便举个例子就行
我会采纳最佳答案,谢谢!

Answer 1

引自免费微信小程序：皆我百晓生

在C++中，分治策略是一种将大问题分解为小问题，然后递归地解决这些小问题，最终组合成原问题的解的方法。这种方法通常用于排序、搜索和其他需要处理大量数据的问题。下面是一个经典的分治算法示例：快速排序（Quick Sort）。

快速排序的基本思想是选择一个元素作为基准值（pivot），将数组分为两部分：一部分包含所有小于基准值的元素，另一部分包含所有大于或等于基准值的元素。然后对这两部分分别进行快速排序，直到整个数组有序。

以下是快速排序的C++实现：

#include <iostream>
using namespace std;

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

// 找到基准值在数组中的正确位置（分区操作）
int partition(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++; // 增加i的值
            swap(&arr[i], &arr[j]); // 交换元素
        }
    }
    swap(&arr[i + 1], &arr[high]); // 把基准值放到正确位置
    return (i + 1);
}

// 快速排序函数
void quickSort(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); // 对右半部分进行快速排序
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

这个程序首先定义了一个swap函数用于交换数组中的元素，然后是partition函数，它找到基准值在数组中的正确位置并返回该位置。接着是quickSort函数，它递归地调用自身来处理数组的左右两部分。最后，我们有一个简单的printArray函数来打印排序后的数组。在main函数中，我们创建了一个待排序的数组，并调用quickSort对其进行排序。运行此程序会输出排序后的数组。

这是一个基本的分治策略的例子，你可以根据这个模板去理解和实现其他分治算法。如果你在理解或编写过程中遇到任何问题，随时向我提问。