我正在学习实现一个用于计数反转的mergesort算法。这是我目前对mergesort的实现。但是,它不起作用,因为它不返回已排序的数组。有人能告诉我在我写的这段代码中做错了什么吗?它应该对输入到函数中的数组v进行排序。
void mergeCountInversion(vector<int> v, int l, int r)
{
if (l >= r)
{
return;
}
int m = (l + r)/2;
//call merge sort to return two sorted arrays
mergeCountInversion(v, l, m);
mergeCountInversion(v, m+1, r);
int left = l;
int right = m+1;
std::vector<int> vtemp ;
//merge and sort the two sorted array, storing the sorted array in vtemp
for (int k = l; k <= r; ++k){
if (left >= m+1)
{
vtemp.push_back(v[right]);
right++;
}
else if (right > r)
{
vtemp.push_back(v[left]);
left++;
}
else
{
if (v[left] <= v[right])
{
vtemp.push_back(v[left]);
left++;
}
else{
vtemp.push_back(v[right]);
right++;
count += m + 1 - left;
}
}
}
//replace v with the sorted array vtemp
for (int i = 0; i < vtemp.size(); ++i)
{
v[l+i] = vtemp[i];
}
}
您的代码中存在几个问题。
您是按值传递向量,但应该按引用传递。
如果您将函数声明为void
,则不能声明return 0;
,只能声明return;
。
当您创建vtemp
时,您应该确切地知道它的大小:r-l。因此,您可以为它保留内存,而不需要push_back。
您还必须将count传递给函数。
您的功能可以是:
void mergeCountInversion(vector<int> & v, int l, int r, int & count) {
if (l >= r) return;
int m = (l + r)/2;
//call merge sort to return two sorted arrays
mergeCountInversion(v, l, m, count);
mergeCountInversion(v, m+1, r, count);
int left = l;
int right = m+1;
std::vector<int> vtemp(r-l);
//merge and sort the two sorted array, storing the sorted array in vtemp
for (int k = l; k <= r; ++k) {
if (left >= m+1) {
vtemp[k] = v[right];
right++;
}
else if (right > r) {
vtemp[k] = v[left];
left++;
}
else {
if (v[left] <= v[right]) {
vtemp[k] = v[left];
left++;
}
else {
vtemp[k] = v[right];
right++;
count += m + 1 - left;
}
}
}
//replace v with the sorted array vtemp
for (int i = 0; i < vtemp.size(); ++i)
v[l+i] = vtemp[i];
}
您定义了
void mergeCountInversion(vector<int> v, int l, int r)
然后首先递归调用mergeCountInversion
,并在调用返回后修改v
。
问题是,在递归调用中对v
所做的更改将永远不会被看到,因为v
是通过值传递的。
尝试通过引用传递v
:
void mergeCountInversion(vector<int>& v, int l, int r)
使得所有调用都在CCD_ 10的同一副本上工作。