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

Question

目前，我正在尝试创建一个简单的 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;
}

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

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();

但这显然行不通

Answer 1

问题是 merge_sort 的类型签名假定了一个就地算法：

void merge_sort(Iterator begin, Iterator end);

但是您的 merge 过程不是就地的，而是 return 是数组的合并副本。您要么需要将 merge 更改为就地，要么需要将 merge_sort 更改为 return 排序数组。后一种解决方案（更简单但效率较低）是这样的：

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());
}

Answer 2

一种优化的自上而下合并排序，一次性分配第二个向量，然后使用一对相互递归函数（...AtoA，...AtoB）根据级别交替合并方向的递归。（我遗漏了原型）。

void MergeSort(     typename std::vector<int>::iterator &ab,
                    typename std::vector<int>::iterator &ae)
{
    size_t sz = ae - ab;
    if (sz < 2)
        return;
    std::vector<int> vb(sz);           // temp vector
    std::vector<int>::iterator bb = vb.begin();
    std::vector<int>::iterator be = vb.end();
    MergeSortAtoA(ab, ae, bb, be);
}

void MergeSortAtoA( typename std::vector<int>::iterator &ab,
                    typename std::vector<int>::iterator &ae,
                    typename std::vector<int>::iterator &bb,
                    typename std::vector<int>::iterator &be)
{
    size_t sz = ae - ab;
    if(sz < 2)                              // if 1 element return
        return;
    std::vector<int>::iterator am = ab+(sz/2);
    std::vector<int>::iterator bm = bb+(sz/2);
    MergeSortAtoB(ab, am, bb, bm);
    MergeSortAtoB(am, ae, bm, be);
    Merge(bb, bm, be, ab);
}

void MergeSortAtoB( typename std::vector<int>::iterator &ab,
                    typename std::vector<int>::iterator &ae,
                    typename std::vector<int>::iterator &bb,
                    typename std::vector<int>::iterator &be)
{
    size_t sz = ae - ab;
    if(sz < 2){                             // if 1 element, copy it
        *bb = *ab;
        return;
    }
    std::vector<int>::iterator am = ab+(sz/2);
    std::vector<int>::iterator bm = bb+(sz/2);
    MergeSortAtoA(ab, am, bb, bm);
    MergeSortAtoA(am, ae, bm, be);
    Merge(ab, am, ae, bb);
}

void Merge(         typename std::vector<int>::iterator &ab,
                    typename std::vector<int>::iterator &am,
                    typename std::vector<int>::iterator &ae,
                    typename std::vector<int>::iterator &bb)
{
std::vector<int>::iterator mb = ab;    // left  run iterator
std::vector<int>::iterator mm = am;    // right run iterator
std::vector<int>::iterator bi = bb;    // merge run iterator

    while(1){                               // merge data
        if(*mb <= *mm){                     // if mb <= mm
            *bi++ = *mb++;                  //   copy mb
            if(mb < am)                     //   if not end left run
                continue;                   //     continue (back to while)
            while(mm < ae)                  //   else copy rest of right run
                *bi++ = *mm++;
            break;                          //     and return
        } else {                            // else mb > mm
            *bi++ = *mm++;                  //   copy mm
            if(mm < ae)                     //   if not end of right run
                continue;                   //     continue (back to while)
            while(mb < am)                  //   else copy rest of left run
                *bi++ = *mb++;
            break;                          //     and return
        }
    }
}

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

C++ Merge Sort using iterators

c++

sorting

algorithm

mergesort