algorithm - 线性排序算法

Question

我是学习算法的新手，也不是计算机科学专业的毕业生。
然而，在阅读线性排序非比较算法时，我可以理解基数排序是计数排序的扩展。
我不清楚的是计数排序的局限性。
当计数排序似乎可以满足我需要避免 O(n*logn) 比较的目的时，为什么我会选择基数排序？
它确实看起来确实是一个更简单的实现。

Answer 1

想象一下，有人给了您一个要排序的整数列表。除了它包含整数外，您对它一无所知。

如果幸运的话，该列表可能包含相当严格的范围内的数字。如果您要对所有介于 -100 和 100 之间的整数进行排序，那么创建一个具有该大小的数组以进行计数排序一点也不坏。

但是即使一个数字非常大或非常小，您现在也必须扩展数组的边界才能对整个输入进行计数排序。如果你真的想对所有可能的整数进行排序(并且在创建数组之前你不知道值的范围，除非你先找到它)，你需要制作一个大小为 2 * max_int 的数组(对于负整数和正整数)。

基数排序很好，因为您永远不需要创建大小大于数字范围 (0-9) 的数组。