C ++使用迭代器合并排序

debugcn 发表于 Dev

vnikonov_63

当前，我正在尝试创建一个简单的C ++合并排序程序。

using namespace std;

using Iterator = std::vector<int>::iterator;
using CIterator = std::vector<int>::const_iterator;
std::vector<int> merge(CIterator left_begin, CIterator left_end, CIterator right_begin, CIterator right_end) {
    std::vector<int> result;
    
    CIterator left = left_begin;
    CIterator right = right_begin;
    
    while (left != left_end && right != right_end) {
        if (*left <= *right) {
            result.push_back(*left);
            left++;
        } else {
            result.push_back(*right);
            right++;
        }
    }
    
    while (left != left_end) {
        result.push_back(*left);
        left++;
    }
    
    while (right != right_end) {
        result.push_back(*right);
        right++;
    }
    
    return result;
}

我创建了一个合并函数，该函数基本上将两个排序的向量连接为一个并返回它（我必须使用函数合并的以下返回类型）。然后尝试编写驱动程序功能合并排序，我有以下代码，我认为工作正常

void merge_sort(Iterator begin, Iterator end) {
    auto difference = distance(begin, end);
    
    if (difference <= 1) {
        return;
    }
    
    Iterator middle = begin;
    advance(middle, difference / 2);
    
    merge_sort(begin, middle);
    merge_sort(middle, end);
    
    vector<int> result = merge(begin, middle, middle, end);
    // But what to put here?
}

在注释标记处，我不知道要写什么才能将排序后的数组向上移动。我试过了

    begin = result.begin();
    end = result.end();

但这显然不起作用

奥尔普

问题在于类型的签名merge_sort采用就地算法：

void merge_sort(Iterator begin, Iterator end);

但是您的merge过程不是就地执行，而是返回数组的合并副本。您要么需要更改merge就位，要么需要更改merge_sort以返回排序后的数组。后一种解决方案（更简单但效率更低）将如下所示：

std::vector<int> merge_sort(Iterator begin, Iterator end) {
    auto difference = distance(begin, end);
    
    if (difference <= 1) {
        return;
    }
    
    Iterator middle = begin;
    advance(middle, difference / 2);
    
    std::vector<int> left = merge_sort(begin, middle);
    std::vector<int> right = merge_sort(middle, end);
    return merge(left.begin(), left.end(), right.begin(), right.end());
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。