为什么在这个合并排序中我会遇到内存问题?

问题描述 投票:0回答:1

我尝试为合并排序编写函数,但是当我尝试调试它时,我得到的是“堆栈溢出”还是“写入地址时违反访问权限”。可能是什么问题???

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

我不明白这里出了什么问题......

sorting debugging memory mergesort
1个回答
0
投票

评论中指出的修复:

#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;
}
© www.soinside.com 2019 - 2024. All rights reserved.