C ++中带有std :: vector的快速排序,EXC_BAD_ACCESS代码2

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

VS代码在运行我的快速排序算法时捕获了此异常:EXC_BAD_ACCESS(代码= 2,地址= 0x7ffeef3ffffc)。这发生在partition()的第一行:

int i = p;

我已经尝试实现Cormen算法:http://www.cs.fsu.edu/~lacher/courses/COP4531/lectures/sorts/slide09.html

为什么我不能访问变量p?它已发布,如果是,该如何解决?

我的代码

//.h file
void sortVector(vector<int> &vec, int p=0, int r=-2);
int partition(vector<int> &vec, int p, int r);

//.cpp file
int partition(vector<int> &vec, int p, int r) {
    int i = p;
    for (int j = p; j <r-1; ++j) {
        if (vec[j] < vec[r-1]) {
            swap(vec[j], vec[r-1]);
            i++;
        }
        swap(vec[i], vec[r-1]);
    }
    return i;
}

void sortVector(vector<int> &vec, int p, int r) {
    if (r == -2) {
        r = vec.size();
    }
    if (p-r<1) {
        int q = partition(vec, p, r);
        sortVector(vec, p, q);
        sortVector(vec, q+1, r);
    }

}

我包括来自Stroustrup的“ std_lib_facilities.h”:使用C ++的编程原理和实践。

c++ sorting quicksort exc-bad-access stdvector
2个回答
1
投票

您需要从swap(vec[i], vec[r-1]);循环中写入for

应该是这样-

//.cpp file
int partition(vector<int> &vec, int p, int r) {
    int i = p;
    for (int j = p; j <r-1; ++j) {
        if (vec[j] < vec[r-1]) {
            swap(vec[j], vec[r-1]);
            i++;
        }
    }
    swap(vec[i], vec[r-1]);

    return i;
}

1
投票

两个功能都存在问题:

partition():

  • 第一次交换有错误的论点。
  • 第二个交换必须移出for循环(由Faruk Hossain建议)
  • if (vec[j] < vec[r-1])变为if (vec[j] <= vec[r-1])

sortVector():

  • [if (p-r<1)成为(p<r)] >>
  • 下面的工作代码。

int partition(vector<int> &vec, int p, int r) {
    int i = p;
    for (int j = p; j <r-1; ++j) {
        if (vec[j] <= vec[r-1]) {
            swap(vec[i], vec[j]);
            i++;
        }
    }
    swap(vec[i], vec[r-1]);
    return i;
}
void sortVector(vector<int> &vec, int p, int r) {
    if (r == -2) {
        r = vec.size();
    }
    if (r>p) {
        int q = partition(vec, p, r);
        sortVector(vec, p, q);
        sortVector(vec, q+1, r);
    }

}
© www.soinside.com 2019 - 2024. All rights reserved.