我是学习算法的新手,也不是计算机科学专业的毕业生。
然而,在阅读线性排序非比较算法时,我可以理解基数排序是计数排序的扩展。
我不清楚的是计数排序的局限性。
当计数排序似乎可以满足我需要避免 O(n*logn) 比较的目的时,为什么我会选择基数排序?
它确实看起来确实是一个更简单的实现。
最佳答案
想象一下,有人给了您一个要排序的整数列表。除了它包含整数外,您对它一无所知。
如果幸运的话,该列表可能包含相当严格的范围内的数字。如果您要对所有介于 -100 和 100 之间的整数进行排序,那么创建一个具有该大小的数组以进行计数排序一点也不坏。
但是即使一个数字非常大或非常小,您现在也必须扩展数组的边界才能对整个输入进行计数排序。如果你真的想对所有可能的整数进行排序(并且在创建数组之前你不知道值的范围,除非你先找到它),你需要制作一个大小为 2 * max_int 的数组
(对于负整数和正整数)。
基数排序很好,因为您永远不需要创建大小大于数字范围 (0-9) 的数组。
关于algorithm - 线性排序算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17641858/