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

Question

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

为此，我的代码如下：

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

>

我知道来自合并的这个数组是一个本地数组，因此我将它返回给mergesort，而mergesort又将它返回给main。假设这不会从后续的递归调用中传入和传出，我是否错了？

我对这段代码的测试输入是{1,0,9}。我应该得到{0,1,9}，但我得到32767。

我错过了什么？

Answer 1

首先对于merge——应该将常量引用传递给参数，否则会产生太多不必要的副本。此外，当您在empty中创建并按索引访问时，还可以访问结果。使用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;
}

Answer 2

对MergeSort的递归调用不起任何作用，因为intArr是按值（复制）获取的，而您没有使用结果值。

像这样的方法应该有用：

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

recresult = merge(newLeft, newRight);

正如Slava在评论中提到的，在访问结果时也有UB，因为它的大小为0：

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

在使用操作符[]访问元素之前，应该调用std:：vector:：resize。