c - 对于不同顺序的数据，基数排序算法可能具有不同的运行时？

我正在尝试实现基数排序算法。
我使用一个链表来存储要排序的元素，然后将每个元素放入它的bucket中。这个bucket只是一个指针，它将链接属于它的bucket的元素列表。
我用区间[1000000]中的10.000.000和100.000.000整数进行测试。这个数字可以是新月形的，递减的和随机的顺序。
以新月和递减顺序运行100000.000个数字的时间约为20秒但对于相同数量的元素具有随机顺序
运行时间大约是110秒。
据我所知，该算法对于任何质量都具有相同的复杂性。
要排序的数据。
有人知道为什么会这样吗？
这是我的代码：

    void radix(Number** numbers)
    {
        unsigned int i, k, e = 1;
        Number* bucket[10];
        Number* tail[10];
        Number* index;

        for(k = 0; k < 7; k++, e *= 10)
        {
            for(i = 0; i < 10; i++) bucket[i] = tail[i] = NULL;

            index = *numbers;
            while(index != NULL)
            {
                i = (index->value / e) % 10;

                if(tail[i] == NULL)
                    bucket[i] = index;
                else
                    tail[i]->next = index;

                tail[i] = index;
                index = index->next;
            }

            for(i = 0; i < 10; i++)
            {
                if(tail[i] != NULL)
                {
                    *numbers = bucket[i];
                    index = tail[i];
                    for(i++; i < 10; i++)
                    {
                        if(tail[i] != NULL)
                        {
                            index->next = bucket[i];
                            index = tail[i];
                        }
                    }
                }
            }

            index->next = NULL;
        }
    }

其中Number是：

typedef struct number
{
    unsigned int value;
    struct number* next;
} Number;

最佳答案

答案可能与内存访问和引用的位置有关。
升序/降序有一个规则模式，它可能具有更大的时间局部性，与其说是关于存储桶，不如说是关于链表节点用于数字的方式（特别是如果它们不是连续的）。
例如，如果我们接受输入：

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...

我们从bucket 0循环到bucket 9，然后返回bucket 0。当我们回到bucket 0时，我们访问的是一个number节点，这个节点最近才访问过（9次迭代前），它可能被缓存到一个更快、更小的内存中。
如果我们使用随机排序，谁知道我们什么时候会回到bucket 0？因此，在返回到用于任何给定bucket头上的数字的内存之前，我们很有可能需要长时间将数据从DRAM移动到缓存结果可以转化为更多这样的前number节点被逐出缓存，当我们回到这样一个bucket时，会有更多的缓存未命中。
对于不规则的排序，分支预测失误也可能会占用一些时间。分析应该有助于缩小原因的范围。
如果你真的是内存瓶颈的话，一个可能的尝试就是把你的存储桶变成，比如说，展开的列表，你可以把这些数字复制到其中。这将使您不再访问以前插入的数字的内存，这些数字可能已经被多次迭代插入回来（由于随机顺序，可能是一个很大的变量）这样，我们就可以得到一些时间位置（如果数字是连续分配的，可能还有空间位置），否则我们将失去这种链表表示。然后它就变成了重用bucket（只有10个）的连续内存，而不是在bucket中的元素，而在bucket之间有可变的步幅我们还得到了具有展开表示的bucket中的空间局部性。
但如果是相同的数据，只是顺序不同，这可能会影响
很多？20到110秒对于相同的数据来说太多了。
记忆效率可以在数量级上产生差异。http://lwn.net/Articles/250967/
我不是这方面的专家（更多的是“分析它并尝试根据指导原则进行优化”类型），但是根据我从内存优化中获得的过去的结果，我经常会将它们与算法优化的效果放在同等的位置。例外将是当复杂性的差异是粗大的（EX：线性化与二次），但即使是线性化算法可以非常可行地击败一个线性的一个非常大的输入，如果前者更明显的缓存友好。

关于c - 对于不同顺序的数据，基数排序算法可能具有不同的运行时？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33928819/