c++ 逆序计数排序向量解除分配

xe55xuns 于 2023-03-05 发布在其他

关注(0)|答案(2)|浏览(173)

我正在学习排序算法的工作原理，我已经用C++实现了计数排序：

vector<int> counting_sort_dec(vector<int> &A, int k) {
    vector<int> B(A.size());
    vector<int> C(k + 1);

    for (int i = 0; i < A.size(); i++)
        C[A[i]]++;

    for (int i = C.size() - 1; i >= 0; i--)
        C[i - 1] += C[i];

    for (int i = 0; i < A.size(); i++) {
        C[A[i]]--;
        B[C[A[i]]] = A[i];
    }
    return B;
}

int main() {
    vector<int> A = {2, 5, 3, 0, 2, 3, 0, 3};

    cout << "Counting sort" << endl;
    for (auto e : A)
        cout << e << " ";
    cout << endl;

    vector<int> A_sorted = counting_sort_dec(A, 5);
    for (auto e : A_sorted)
        cout << e << " ";
    cout << endl << endl;
    
    return 0;
}

当我在return B;处停止调试器时，我看到一个正确排序的数组[5, 3, 3, 3, 2, 2, 0, 0];然而，在此之后，程序崩溃，退出代码为134（被信号6：SIGABRT）.看起来向量B在返回之前就释放了.我怎么才能说服它不这样做呢？最奇怪的是我写了一个函数，它按升序排序，而且它工作起来没有任何问题：

vector<int> counting_sort(vector<int> &A, int k) {
    vector<int> B(A.size());
    vector<int> C(k + 1);

    for (int i = 0; i < A.size(); i++)
        C[A[i]]++;

    for (int i = 1; i < C.size(); i++)
        C[i] += C[i - 1];

    for (int i = A.size() - 1; i >= 0; i--) {
        C[A[i]]--;
        B[C[A[i]]] = A[i];
    }
    return B;
}

降序有什么问题？

c++

来源：https://stackoverflow.com/questions/75582517/reverse-order-count-sort-vector-deallocation

2条答案

按热度按时间

vlju58qv1#

在您的counting_sort_dec函数中，第二个for循环具有错误的限制。当i为零时，C[i - 1]表达式引用了越界数组元素，并导致未定义的行为-这可以用许多不同的方式来表达自己（例如在程序执行过程中稍后崩溃）。
在第二个循环中将循环终止测试从i >= 0更改为i > 0：

vector<int> counting_sort_dec(vector<int>& A, int k) {
    vector<int> B(A.size());
    vector<int> C(k + 1);

    for (int i = 0; i < A.size(); i++)
        C[A[i]]++;

    for (int i = C.size() - 1; i > 0; i--) // Don't run loop when i is zero
        C[i - 1] += C[i];

    for (int i = 0; i < A.size(); i++) {
        C[A[i]]--;
        B[C[A[i]]] = A[i];
    }
    return B;
}

注意，使用std::vector的.at(i)成员函数（而不是使用[i]直接访问元素）将有助于捕获这类错误，因为std::out_of_bounds异常将在错误发生时**抛出（而不是在执行过程中稍后的某个任意时刻）。
在（工作中的）升序排序中，第二个循环从索引i = 1开始，因此降序排序中应该在该点结束似乎是合理的，因为这两个循环的其他限制是相同的（即C.size() - 1）。

赞(0）回复(0）举报 2023-03-05

wwtsj6pe2#

看起来你这里有一个bug：

for (int i = C.size() - 1; i >= 0; i--)
        C[i - 1] += C[i];

当i等于0时，程序崩溃

赞(0）回复(0）举报 2023-03-05

我来回答

c++ 逆序计数排序向量解除分配

2条答案

相关问题

热门标签

最新问答