计数排序不同的方法

计数排序通常在我们知道 正面的 这些值将被限制在一定的范围内。

这个范围不需要从零开始;使用一个长度为6的数组是完全可以的,该数组的元素表示值95到100的计数(或者,就此而言,值的计数从-2到3)。所以,是的,你的方法仍然是“计数排序”。

但是,如果您事先不知道这个限制,那么您不太可能通过对要检查的数据进行完整的传递来获得更快的结果。

例如:假设您有1000000个元素,并且 知道 它们都在0-200范围内,但你认为它们是 可能 都在更窄的范围内。好吧,预扫描整个输入数组的成本将大于使用201元素工作数组的成本,这意味着它的成本比仅进行范围为0-200的计数排序可能节省的成本要高。

此方法的运行时为o(n+max值)。

运行时是 o (max(num_元素,range_大小)),由于landau(big-o)符号的魔力,它与 o (num_元素+范围大小)。如果max_值的渐进性大于num_元素和range_大小,则方法只影响渐进复杂性。