在c++中使用向量实现合并排序。

Question

我试图在C++中使用向量实现合并排序，这是我正在执行的以下代码。

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int> &a,int l,int m,int r)
{
    int i,j,k;
    int n1 = m-l+1;
    int n2=r-m;

    int L[n1],R[n2];
    for(i=0;i<n1;i++)
    {
        L[i]=a[l+i];
    }
    for(j=0;j<n2;j++)
    {
        L[j]=a[m+1+j];
    }
    i=0;
    j=0;
    k=l;     //merged array
    while(i<n1 && j<n2)
    {
        if(L[i]<=R[j])
        {
            a[k]=L[i];
            i++;
        }
        else
        {
            a[k]=R[j];
            j++;
        }
        k++;
    }
    while(i<n1)
    {
        a[k]=L[i];
        i++;
        k++;
    }
    while(j<n2)
    {
        a[k]=R[j];
        j++;
        k++;
    }
}


void mergeSort(vector<int> &a, int l, int r) 
{
  if(l<r)
  {
    int m = l+(r-l)/2;
    mergeSort(a,l,m);
    mergeSort(a,m+1,r);
    merge(a,l,m,r);
  }
}

int main() {
  int n;
  std::cin >> n;
  vector<int> a(n);
  for (int i = 0; i < a.size(); i++) {
    cin >> a[i];
  }
  mergeSort(a,0,a.size()-1);
  for (int i = 0; i < a.size(); i++) {
    cout << a[i];
  }
}

当我执行这段代码并输入任何值时 我在数组中得到的是垃圾值。a[i] = 7405024, 代码给我出错是由于我不能就地改变向量的值还是有其他原因。

Answer 1

问题在于 merge 功能

for(j=0;j<n2;j++)
{
    R[j]=a[m+1+j]; // not L[j]
}

由于你是用向量来实现的，建议你改成 L 和 R 到向量。C++默认不支持VLA。一些编译器可能会接受，但应该避免完全使用。

std::vector<int> L(n1);
std::vector<int> R(n2);

Answer 2

我看到的一个明显的变化是

IN merge() function

for(j=0;j<n2;j++)
{
    R[j]=a[m+1+j];
}

因为这些值必须存储在 RIGHT 矢量。