我是研究算法的新手 - 我也不是计算机科学毕业生。
然而，在阅读线性排序非比较算法时，我可以理解基数排序是计数排序的扩展。
我不清楚的是计数排序的局限性。
当计数排序似乎可以满足我需要避免 O(n*logn) 比较的目的时，为什么我要选择基数排序？
这确实看起来是一个更简单的实现。
想象一下有人给了你一个要排序的整数列表。除了它包含整数之外，您对它一无所知。
如果幸运的话，该列表可能包含相当严格范围内的数字。如果您要对 -100 到 100 之间的整数进行排序，那么创建一个具有该大小的数组来进行计数排序一点也不坏。
但是，即使有一个数字非常大或非常小，您现在也必须扩展数组的边界，以便对整个输入进行计数排序。如果您确实想对所有可能的整数进行排序（并且在创建数组之前您不知道值的范围，除非您先找到它），则需要创建一个 size 的数组2 * max_int（对于负整数和正整数）。
基数排序很好，因为您永远不需要创建大小大于数字范围 (0-9) 的数组。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
