合并排序 - return 一个新数组，而不是将合并后的数组复制到输入数组

Question

我正在尝试实现一个非常简单的合并排序版本（不考虑为此目的进行的所有优化），我的目标是 return 合并数组的新副本而不是传统方式通过引用传递输入数组并将合并的元素复制到其中。

为此，我的代码如下：

vector<int> merge(vector<int> left, vector<int> right)
{
    vector<int> result;
    int leftIdx = 0;
    int rightIdx = 0;
    int resultIdx = 0;

    while (leftIdx < left.size() && rightIdx < right.size()) {
        if (left[leftIdx] < right[rightIdx]) {
            result[resultIdx++] = left[leftIdx++];
        } else {
            result[resultIdx++] = right[rightIdx++];
        }
    }

    while (leftIdx < left.size()) {
        result[resultIdx++] = left[leftIdx++];
    }

    while (rightIdx < right.size()) {
        result[resultIdx++] = right[rightIdx++];
    }

    return result;
}

vector<int> MergeSort(vector<int> intArr)
{
    vector<int> recresult;

    // base - if array is of length 1, nothing to do, return it as is
    if (intArr.size() == 1) {
        return intArr;
    } else {
        int mid = intArr.size() / 2;
        // copy left half
        vector<int> leftArr(intArr.begin(), intArr.begin() + mid);
        // copy right half
        vector<int> rightArr(intArr.begin() + mid, intArr.end());

        MergeSort(leftArr);
        MergeSort(rightArr);

        recresult = merge(leftArr, rightArr);
    }

    return recresult;
}

我知道这个来自 merge 的数组是一个本地数组，因此我 return 将它合并到 mergesort，后者又 return 它到 main。我假设这不会传入和传出是错误的吗后续的递归调用？
我对此代码的测试输入是 {1,0,9}。我应该得到 {0,1,9} 但我得到 32767.

我在这里错过了什么？

Answer 1

对 MergeSort 的递归调用没有任何作用，因为 intArr 被值 （已复制） 接受，而您没有使用结果值。

像这样的东西应该可以工作：

auto newLeft = MergeSort(leftArr);
auto newRight = MergeSort(rightArr);

recresult = merge(newLeft, newRight);

正如Slava在评论中提到的，访问result时也有UB，因为它的size是0:

vector<int> result; // size = 0
// ...
result[resultIdx++] = left[leftIdx++]; // UB!

您应该在使用 operator[] 访问元素之前调用 std::vector::resize。

Answer 2

首先是 merge - 你应该将 const 引用传递给参数，否则你会制作太多不必要的副本。当您在空中创建并按索引访问时，您也可以不受限制地访问 result 。使用 int 作为索引也不是一个好主意。所以简化版本可以是：

vector<int> merge(const vector<int> &left, const vector<int> &right)
{
    vector<int> result;
    auto lit = left.begin();
    auto rit = right.begin();
    while( lit != left.end() || rit != right.end() ) {
        bool lft = false;
        if( rit == right.end() )
            lft = true;
        else {
            if( lit != left.end() )
                lft = *lit < *rit;
        }
        result.push_back( lft ? *lit++ : *rit++ );
   }
   return result;
}

或更接近您的版本：

vector<int> merge(const vector<int> &left, const vector<int> &right)
{
    vector<int> result( left.size() + right.size() );
    auto rst = result.begin();
    auto lit = left.begin();
    auto rit = right.begin();
    while( lit != left.end() && rit != right.end() )
        *rst++ = *lit < *rit ? *lit++ : *rit++;

    std::copy( lit, left.end(), rst );
    std::copy( rit, right.end(), rst );
    return result;
}

合并排序 - return 一个新数组，而不是将合并后的数组复制到输入数组

Merge Sort - return a new array instead of copying merged array to input array

c++

arrays

sorting

algorithm

mergesort