使用 std::vector、EXC_BAD_ACCESS 代码 2 在 C++ 中进行快速排序

Question

当我运行我的快速排序算法时，VS Code 捕获了这个异常： 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++ 的编程原则和实践。

Answer 1

您需要在 for 循环之外编写 swap(vec[i], vec[r-1]);。

应该是这样的-

//.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;
}

Answer 2

两个函数都有问题：

分区():

第一次交换有错误的参数。
第二个交换必须移出 for 循环（由 Faruk Hossain 建议）
if (vec[j] < vec[r-1]) 变成了 if (vec[j] <= vec[r-1])

排序向量():

if (p-r<1) 变成了 if (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);
    }

}

使用 std::vector、EXC_BAD_ACCESS 代码 2 在 C++ 中进行快速排序

Quicksort in C++ with std::vector, EXC_BAD_ACCESS code 2

c++

sorting

quicksort

exc-bad-access

stdvector

我的代码