algorithm - 排序整数

Question

我是算法艺术和科学的初学者，当我学习“快速排序”(据称速度非常快)时，我想到了一种使用字典的排序方法。我对它进行了编码，令我感到非常惊讶的是，对于我感兴趣的内容(例如，排序地球温度或海拔数据)，我编码的内容实际上比 C# .NET 的列表更快。 Sort() 一旦我在 Release模式下编译它。例如，如果我创建一个包含 100 万个整数的列表，其中加载了 0 到 8000 之间的值(典型地球海拔的良好范围)，.NET List.Sort() 方法平均需要大约 88 毫秒来对列表进行排序，而下面的算法在大约 58 毫秒内完成。 所以这让我想到我应该获得诺贝尔计算机科学奖(不太可能)或者我缺少一些东西并且有一种更有效的方法来对范围内的大量整数进行排序说从零到 10,000。专家们如何对该范围内的大量数据进行排序？

private static long DictionarySort(List<int> myList, out List<int> sortedList)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    int max = myList.Max();
    Dictionary<int, int> sorter = new Dictionary<int, int>();
    int myListCount = myList.Count;
    for (int i = 0; i < myListCount; i++)
    {
        int val = myList[i];
        int occurances = 0;
        sorter[val] = sorter.TryGetValue(val, out occurances) ? occurances + 1 : 1;
    }
    sortedList = new List<int>(myList.Count + 1);
    int numOccur = 0;
    for (int i = 0; i <= max; i++)
    {
        if (sorter.TryGetValue(i, out numOccur))
        {
            for (int j = 0; j < numOccur; j++)
            {
                sortedList.Add(i);
            }
        }
    }
    sw.Stop();
    return sw.ElapsedMilliseconds;
}

Answer 1

您重新发现了维基百科所谓的 counting sort ，一个非常简单的分布排序算法。它是您数据集的最佳算法:它在 O(N + k) 时间内运行(N 是记录数，k 是不同键的数量)，使用 O(k) 额外存储，并且系数非常低。