分治法实现三路归并排序c++完整代码

分治法是一种常见的算法设计策略，用于解决可以分解成较小独立部分的问题。三路归并排序（Three-Way Merge Sort）是归并排序的一种变体，特别适合处理已经部分有序的数据。它将数组分成三个部分：小于、等于和大于中间值的部分，然后递归地对每一部分进行排序，最后合并结果。

以下是C++中使用分治法实现三路归并排序的一个简短版本：

#include <vector>
using namespace std;

// 定义辅助函数，用于合并三个已排序区间
void merge(vector<int>& arr, int low, int mid, int high) {
    int i = low;        // 小于区间的指针
    int j = mid + 1;    // 大于区间的指针
    int k = low;        // 合并结果的指针
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            arr[k++] = arr[i++];
        } else {
            arr[k++] = arr[j++];
        }
    }

    // 把剩余的小于元素复制到结果
    while (i <= mid) {
        arr[k++] = arr[i++];
    }

    // 把剩余的大于元素复制到结果
    while (j <= high) {
        arr[k++] = arr[j++];
    }
}

// 主函数，三路归并排序
void threeWayMergeSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // 找到中间点
        int mid = (low + high) / 2;
        // 分别对小于、等于、大于中间值的区间进行排序
        threeWayMergeSort(arr, low, mid);
        threeWayMergeSort(arr, mid + 1, high);

        // 合并这三个已排序区间
        merge(arr, low, mid, high);
    }
}

// 测试代码
int main() {
    vector<int> vec = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    int n = vec.size();
    threeWayMergeSort(vec, 0, n - 1);
    for (auto& num : vec) {
        cout << num << " ";
    }
    return 0;
}