如何为已实现的归并排序模板函数添加自定义比较器

嘿，你已经搞定了模板化的归并排序，距离支持自定义排序逻辑只差最后几步啦！下面我会一步步带你实现这个功能，代码示例和注意事项都给你安排得明明白白：

1. 给模板函数添加比较器参数 #

首先，我们需要给归并排序的模板增加一个可选的比较器模板参数，默认使用std::less<T>（也就是升序排序的逻辑）。这样用户既可以用默认行为，也能传入自己的比较器。

同时，在函数参数里也要加上这个比较器的实例（同样给默认值，方便调用）。如果你的归并排序拆分成了merge和mergeSort两个函数，那两个函数都需要加上这个参数哦。

2. 替换排序逻辑中的比较判断 #

原来你代码里直接用left[i] < right[j]这种硬编码的比较，现在要全部替换成用传入的比较器对象来判断。比如把if (a < b)改成if (comp(a, b))，这样就完全交给自定义比较器来决定元素的顺序了。

3. 完整代码示例 #

下面是改造后的完整模板化归并排序代码，包含了简化的对外调用接口：

#include <vector>
#include <functional> // 必须包含这个头文件才能用std::less、std::greater

// 归并操作的模板函数，带比较器参数
template <typename T, typename Comparator = std::less<T>>
void merge(std::vector<T>& arr, int left, int mid, int right, Comparator comp) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<T> leftArr(n1);
    std::vector<T> rightArr(n2);

    // 复制子数组元素
    for (int i = 0; i < n1; ++i)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    // 用自定义比较器替代原有的<判断
    while (i < n1 && j < n2) {
        if (comp(leftArr[i], rightArr[j])) {
            arr[k] = leftArr[i];
            ++i;
        } else {
            arr[k] = rightArr[j];
            ++j;
        }
        ++k;
    }

    // 复制剩余元素
    while (i < n1) {
        arr[k] = leftArr[i];
        ++i;
        ++k;
    }
    while (j < n2) {
        arr[k] = rightArr[j];
        ++j;
        ++k;
    }
}

// 递归的归并排序核心函数，带比较器参数
template <typename T, typename Comparator = std::less<T>>
void mergeSortCore(std::vector<T>& arr, int left, int right, Comparator comp) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 避免溢出的写法

        mergeSortCore(arr, left, mid, comp);
        mergeSortCore(arr, mid + 1, right, comp);

        merge(arr, left, mid, right, comp);
    }
}

// 对外简化的调用接口，无需传入左右边界
template <typename T, typename Comparator = std::less<T>>
void mergeSort(std::vector<T>& arr, Comparator comp = Comparator()) {
    if (!arr.empty()) {
        mergeSortCore(arr, 0, arr.size() - 1, comp);
    }
}

4. 使用示例 #

现在你可以轻松实现各种排序需求了：

默认升序排序 #

std::vector<int> nums = {3, 1, 4, 1, 5, 9};
mergeSort(nums); // 默认使用std::less<int>，输出升序数组

降序排序（用标准比较器std::greater） #

mergeSort(nums, std::greater<int>()); // 输出降序数组

自定义比较器（比如按字符串长度排序） #

std::vector<std::string> strs = {"apple", "banana", "cherry", "date"};
// 用lambda表达式做自定义比较器：按字符串长度从小到大排
auto compareByLength = [](const std::string& a, const std::string& b) {
    return a.size() < b.size();
};
mergeSort(strs, compareByLength);
// 排序后结果：date, apple, banana, cherry

5. 关键注意事项 #

• 头文件依赖：一定要包含<functional>头文件，不然std::less和std::greater这些标准比较器会报错。
• 严格弱序要求：自定义比较器必须满足严格弱序规则，否则排序结果会出现未定义行为。简单来说：
  • comp(a, a)必须返回false
  • 如果comp(a, b)为true，那么comp(b, a)必须为false
  • 如果comp(a, b)和comp(b, c)都为true，那么comp(a, c)也必须为true
• 递归传递比较器：别忘了在递归调用归并排序的时候把比较器传下去，不然递归内部会用默认的比较器，导致逻辑不一致。

内容的提问来源于stack exchange，提问作者Bluefarmer