合并排序显示意外的输出

Question

我写了一个合并排序代码，但它给出了奇怪的输出。我认为问题出在名为“Merge”的函数中，但我不确定它是什么。可能是我复制矢量的方式有误，但我不确定。代码没有给出任何错误，只是给出了不正确的输出

#include<iostream>
#include<vector>
using namespace std;

    void Merge(vector<int>& nums, int s, int e)
    {
        int mid = (s+e)/2;
        int i=s,j=mid+1,MainIndex=s;

        vector<int>Merge;


        while(i<=mid && j<=e)
        {
            if(nums[i]<nums[j])
            Merge.push_back(nums[i++]);

            else if(nums[i]>nums[j])
            Merge.push_back(nums[j++]);
        }

        while(j<=e)
        Merge.push_back(nums[j++]);

        while(i<=mid)
        Merge.push_back(nums[i++]);

        for (int i = 0; i <=e-s+1; ++i)
        nums[MainIndex++] = Merge[i];
    }

    void MergeSort(vector<int>& nums, int s, int e)
    {

        if(s>=e)
        return;

        int mid = (s+e)/2;

        MergeSort(nums,s,mid);
        MergeSort(nums,mid+1,e);

        Merge(nums,s,e);

    }

    vector<int> sortArray(vector<int>& nums)
    {
        MergeSort(nums,0,nums.size()-1);
        return nums;
    }





int main()
{
    vector<int> v = {4,1,3,7,5,9};

    cout<<"Before: ";
    for (int i = 0; i < v.size(); ++i)
    cout<<v[i]<<" ";

    v = sortArray(v);

    cout<<"\nAfter: ";
    for (int i = 0; i < v.size(); ++i)
    cout<<v[i]<<" ";
}

代码没有报错。它给出了错误的输出

Answer 1

问题出在 for 循环中，您将元素从临时 Merge 向量复制回原始 nums 向量。

在循环中，您使用了

i <= e-s+1

作为循环条件。但是，循环应该从

0

到

e-s

包括在内。所以正确的循环条件应该是

i <= e-s

：

for (int i = 0; i <= e-s; ++i)
    nums[MainIndex++] = Merge[I];

运行带有该更改的完整代码：

#include <iostream>
#include <vector>

using namespace std;

void Merge(vector<int> &nums, int s, int e) {
  int mid = (s + e) / 2;
  int i = s, j = mid + 1, MainIndex = s;
  vector<int> Merge;
  while (i <= mid && j <= e) {
    if (nums[i] < nums[j])
      Merge.push_back(nums[i++]);
    else if (nums[i] > nums[j])
      Merge.push_back(nums[j++]);
  }
  while (j <= e)
    Merge.push_back(nums[j++]);
  while (i <= mid)
    Merge.push_back(nums[i++]);
  for (int i = 0; i <= e - s + 1; ++i)
    nums[MainIndex++] = Merge[i];
}

void MergeSort(vector<int> &nums, int s, int e) {
  if (s >= e)
    return;
  int mid = (s + e) / 2;
  MergeSort(nums, s, mid);
  MergeSort(nums, mid + 1, e);
  Merge(nums, s, e);
}

vector<int> sortArray(vector<int> &nums) {
  MergeSort(nums, 0, nums.size() - 1);
  return nums;
}

int main() {
  vector<int> v = {4, 1, 3, 7, 5, 9};
  cout << "Before: ";
  for (int i = 0; i < v.size(); ++i)
    cout << v[i] << " ";
  v = sortArray(v);
  cout << "\nAfter: ";
  for (int i = 0; i < v.size(); ++i)
    cout << v[i] << " ";
}

观察到正确的输出：

Before: 4 1 3 7 5 9 
After: 1 3 4 5 7 9