c++ - 逆序计数排序 vector 重新分配

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)。似乎 vector 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] 表达式引用超出范围的数组元素并导致未定义的行为 - 它可以用许多不同的方式表达自己(例如稍后在执行程序时发生崩溃)。

在第二个循环中将循环终止测试从 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)。