c++ - 这是最快的一位数字排序算法吗？

Question

我正在尝试学习c++并编写了此算法，我想知道是否有更快的方法来完成相同的事情。这是假设输入有效的。我试图考虑如何删除嵌套的for循环，但由于它不是指数形式，因此认为很好。它是否正确？谢谢

void DigitSort(int* arr, int size)
{
    int counts[10] = { 0,0,0,0,0,0,0,0,0,0 };
    int k = -1;
    while (++k < size)
        counts[arr[k]]++;
    k = -1;
    for (int j = 0; j < 10; ++j)
        for (int i = 0; i < counts[j]; ++i)
            arr[++k] = j;
}

Answer 1

没有基准，但是这是一个使用std::fill_n的(可能)更快的解决方案。

void DigitSort(int* arr, int size)
{
    int counts[10] = { 0,0,0,0,0,0,0,0,0,0 };
    int k = -1, sum_count = 0;
    while (++k < size)
        counts[arr[k]]++;
    
    for (k = 0; k < 10; ++k) {
        std::fill_n(arr + sum_count, counts[k], k);
        sum_count += counts[k];
    }
}

当我说“可能”时，是因为编译器可以将std::fill_n优化为 memset-like指令。