逆序计数排序向量释放

Question

我正在学习排序算法的工作原理。我用 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;
}

降序排列有什么问题？

Answer 1

在您的counting_sort_dec函数中，第二个for循环的限制错误。当i为零时，C[i - 1]表达式引用越界数组元素并导致未定义的行为 \xe2\x80\x93 ，它可以以多种不同的方式表达自己（例如稍后在程序执行过程中崩溃）。

\n

在第二个循环中将循环终止测试从 更改为i >= 0：i > 0

\n

vector<int> counting_sort_dec(vector<int>& A, int k) {\n    vector<int> B(A.size());\n    vector<int> C(k + 1);\n\n    for (int i = 0; i < A.size(); i++)\n        C[A[i]]++;\n\n    for (int i = C.size() - 1; i > 0; i--) // Don\'t run loop when i is zero\n        C[i - 1] += C[i];\n\n    for (int i = 0; i < A.size(); i++) {\n        C[A[i]]--;\n        B[C[A[i]]] = A[i];\n    }\n    return B;\n}\n

\n

请注意，使用 的.at(i)成员函数std::vector（而不是使用 的直接元素访问[i]）将有助于捕获此类错误，因为将在错误点std::out_of_bounds引发异常（而不是在执行过程中的某个任意点）

\n\n

在您的（工作）升序排序中，您在索引处开始等效的第二个循环i = 1，因此您应该以降序排序在该点结束似乎是合理的，因为这两个循环的其他限制是相同的（即，C.size() - 1） 。

\n