问是否有可能编写通用的桶排序？

EN

您给出的运行时-- O(n + M) --以及您说的算法只适用于整数的事实使我认为您指的是计数排序而不是桶排序。如果您想知道是否总是能够找到一种方法来为对象提供任意的索引，比如哈希代码，使它们能够计数排序，那么答案是否定的，这并不总是能够做到的。

以字符串为例。假设我们有从字符串到整数的映射，如果str1 < str2，那么代码(Str1)<代码(Str2)。现在，取字符串"“和"b”，确定代码(“”)和代码(“b”)。我们知道代码(“”)<代码(“b”)。现在，定义

K=代码(B)-代码(“”)-1

这是代码(“”)和代码(“b”)之间的整数数，排它。

接下来，考虑字符串"a“、"aa”、"aaa“、”aaa“等，直到我们得到它们中的k+1。请注意

“< "a”< "aa“< "aaa”< "aaaa“<”aaaa“<…< "b”。

这意味着我们应该

代码(“aaa”)<代码(“aaa”)<<.<代码(“b”)

问题是:代码(“”)和代码(“b”)之间只有k个不同的整数值，但是有一些k+1字符串需要填补这些空白。这将迫使两个字符串发生冲突，并具有相同的数字代码，从而导致排序失败。

这是一个问题的原因是，整数不具有与许多其他结构相同的订单类型，例如字符串、整数对、实数等等。