c++ - C++中的计数排序

Question

我正在尝试在不创建函数的情况下在 C++ 中实现计数排序。这是我到目前为止编写的代码，但程序没有返回任何值。它也不给我任何错误。因此，有什么问题吗？

#include <iostream>

using namespace std;

int main()
{
    int A[100], B[100], C[100], i, j, k = 0, n;

    cin >> n;

    for (i = 0; i < n; ++i)
    {
        cin >> A[i];
    }

    for (i = 0; i < n; ++i)
    {
        if (A[i] > k)
        {
            k = A[i];
        }
    }

    for (i = 0; i < k + 1; ++i)
    {
        C[i] = 0;
    }

    for (j = 0; j < n; ++j)
    {
        C[A[j]]++;
    }

    for (i = 0; i < k; ++i)
    {
        C[i] += C[i - 1];
    }

    for (j = n; j > 0; --j)
    {
        B[C[A[j]]] = A[j];
        C[A[j]] -= 1;
    }

    for (i = 0; i < n; ++i)
    {
        cout << B[i] << " ";
    }

    return 0;
}

Answer 1

看来您的方向是正确的。您将输入输入到 A 中，找到您将要处理的最大值，然后确保将 C 数组中的那么多值归零。但那是事情开始出错的时候。然后你做:

for (i = 0; i < k; ++i)
{
    C[i] += C[i - 1];
}

for (j = n; j > 0; --j)
{
    B[C[A[j]]] = A[j];
    C[A[j]] -= 1;
}

第一个循环总是会在第一次迭代时出界(C[i-1] 当 i=0 时将是未定义的行为)，但即使它没有 我不确定你在这里有什么想法。或者在那之后的循环中。

相反，如果我是你，我会创建一个 indx 变量来跟踪我接下来要插入一个数字的索引(到目前为止我已经插入了多少个数字)，然后我会遍历 C 并且对于 C 中的每个值，我会循环那么多次并插入那个索引的那么多值。我的解释可能听起来有点冗长，但看​​起来像:

int indx = 0;
for(int x = 0; x <= k; x++) {
    for(int y = 0; y < C[x]; y++) {
        B[indx++] = x;
    }
}

如果用这个循环替换上面的两个循环，那么一切都应该按预期工作。

请在此处查看实例:ideone