c++ merge如何实现高效合并

在C++中实现高效的合并算法通常使用归并排序（Merge Sort）或者双指针法（Two Pointers）。

归并排序是一种分治算法，它将一个数组分成两部分，分别对这两部分进行排序，然后再合并这两部分。这种方法的时间复杂度为O(nlogn)，其中n为数组的大小。以下是一个使用归并排序实现合并的示例代码：

void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> tmp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    
    for (int m = 0; m < k; ++m) {
        nums[left + m] = tmp[m];
    }
}

void mergeSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

双指针法则是通过创建两个指针分别指向两个数组的开头，然后比较两个指针指向的元素，并将较小的元素放入结果数组中。通过移动指针实现合并。这种方法的时间复杂度为O(n)，其中n为数组的大小。以下是一个使用双指针法实现合并的示例代码：

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

以上是两种常用的合并算法，可以根据具体的需求选择使用哪一种。通过使用这些合并算法，可以实现高效的合并操作。