这是一个已知的排序算法吗？

Question

我正在练习并实现一些众所周知的排序算法，我认为如果我们从侧面查看列表，它应该出现已排序的状态而不需要进行任何操作（请参见代码，它相当自说明）。我很确定这已经被想到/完成了，我想知道它实际上被称为什么。

以下是我的实现方式。我知道当内容的“最大-最小”范围很大时，它的性能会很差，并且可能只适用于整数。 （但是在非常大的列表上，当内容来自某个相对较小的范围时（在我的PC上少于110000000种变化），它看起来非常好地运行）

获取此名称的主要原因是查看进一步的改进和变化：

void MainWindow(){
    for (int a = 0; a < 130000000; a++)
    {
        rList.Add(rand.Next(1, 110000000));
    }
    Thread t1 = new Thread(() =>
    {
        SortYAxis(rList);
    });
}

void SortYAxis(List<int> list)
{
    int max = int.MinValue;
    int min = int.MaxValue;
    foreach (int a in list)//Get max/min range
    {
        if (max < a)
        {
            max = a;
        }
        else if (min > a)
        {
            min = a;
        }
    }

    int[] yList = new int[max - min + 1];
    foreach (int a in list)//Flatten along Y axis
    {
        yList[a - min]++;
    }

    for (int i = 0, a = 0; i < yList.Length; i++)//Read down Y axis
    {
        while (yList[i] != 0)
        {
            list[a++] = i + min;
            yList[i]--;
        }
    }
}

- Thomas Andreè Wang

---

你有什么问题？ - Nir Alfasi

这种类型叫什么？我很确定它像所有其他算法类型一样有一个名称。 - Thomas Andreè Wang

哦，这叫做桶排序，是的 - 当范围不大时，它的时间复杂度为O(n)，非常棒。 - Nir Alfasi

Answer 1

这是一个桶排序。 （你的代码基本上是教科书实现。）

桶排序的效率来自于它不是比较排序 - 数组的元素不相互比较。这就是桶排序可以具有O（n）复杂度，并且“击败”比较排序受限制的标准O（n log（n））限制的原因。

缺点（正如您所推测的那样）是桶排序仅适用于有限集合，即必须有一些有限数量的“桶”可以被创建以容纳任何正在排序的元素。因此，桶排序不能用作浮点值或字符串的排序算法。此外，如果值的“范围”很大，则桶排序具有高空间要求。这些因素往往超过了线性复杂度的好处，因此桶排序很少被使用。

- BJ Myers

---

没问题，你可以把它交给BJ - 我喜欢他的名字:D - Nir Alfasi

@Thomas 当 alfasin 发布他的评论时，我正在输入我的答案 - 直到我完成后才看到它。如果他将其发布为答案，您可以接受他的答案。 - BJ Myers

它的算法复杂度比基于比较的排序算法要好，因此对于大型整数数据集非常有用。但是它不能用作浮点数或字符串的排序算法，这也是它没有得到广泛关注的主要原因。 - BJ Myers

不错的回答，但也许你应该澄清一下整数是一个有限集合的方式 :P - Juan Lopes

@JuanLopes 我稍微完善了我的回答。谢谢你的建议。 - BJ Myers