我尝试为合并排序编写函数,但是当我尝试调试它时,我得到的是“堆栈溢出”还是“写入地址时违反访问权限”。可能是什么问题???
void Merge(vector<int>a, int l, int m, int r) {
int i = l, j = m, k = 0;
vector<int> b(a.size());
while (i < m && j < r) {
if (a[i] < a[j])
b[k] = a[i];
i++
else
b[k] = a[j];
j++;
k++;
}
while (i < m) {
b[k] = a[i];
k++;
i++;
}
while (j < r) {
b[k] = a[j];
k++;
j++;
}
for (int x = 0; x < a.size(); x++)
a[x] = b[x];
delete &b;
}
void Mergesort(vector<int>& a, int l, int r) {
if (l >= r)
return;
int mid = l + (r - l) / 2;
Mergesort(a, l, mid);
Mergesort(a, mid, r);
Merge(a, l, mid, r);
}
int main() {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
Mergesort(a, 0, n-1);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
}
我不明白这里出了什么问题......
评论中指出的修复:
#include <iostream>
#include <vector>
void Merge(std::vector<int>&a, int l, int m, int r) { // fix &a
int i = l, j = m, k = l; // fix k = l
std::vector<int> b(a.size());
while (i < m && j < r) {
if (a[i] <= a[j]) {
b[k] = a[i];
i++;
} else {
b[k] = a[j];
j++;
}
k++;
}
while (i < m) {
b[k] = a[i];
k++;
i++;
}
while (j < r) {
b[k] = a[j];
k++;
j++;
}
for (k = l; k < r; k++) // fix copy back l to r
a[k] = b[k];
// fix b is local, don't delete
}
void Mergesort(std::vector<int>& a, int l, int r) {
if ((r-l) < 2) // r is end instead of last
return;
int mid = l + (r - l) / 2;
Mergesort(a, l, mid);
Mergesort(a, mid, r);
Merge(a, l, mid, r);
}
int Rnd32()
{
static uint32_t r = 0;
r = r*1664525 + 1013904223;
return (int)r;
}
#define n (1024)
int main() {
std::vector<int> a(n);
int i;
for (i = 0; i < n; i++)
a[i] = Rnd32();
Mergesort(a, 0, n); // fix n is end instead of last
for (i = 1; i < n; i++){
if(a[i-1] > a[i])
break;
}
if(i == n)
std::cout << "passed" << std::endl;
else
std::cout << "failed" << std::endl;
return 0;
}