使用散列 table 在计数排序中是否有效（代替数组）？
Is using a hash table valid in counting sort (in place of an array)?
经典的计数排序示例要求您构建一个大小等于输入数组的最大整数的数组。
例如，如果您的数组是 [1, 6, 3, 10000, 8]，您需要一个长度为 10000 的数组来进行计数排序。
难道不能在同一线性时间内对整数使用散列 table 来完成吗？只是一张简单的地图？
在 python 中，它类似于：
counting_map = {n: 0 for n in input_array} # start by mapping all to 0
for num in input_array:
counting_map[n] += 1
我知道这真的只适用于整数，但在那种情况下映射解决方案不是更好吗？
在时间复杂度方面，您在 O(n) 时间内初始化映射，然后在 O(n) 时间内遍历数组，然后在 O(1) 时间内对输入执行哈希函数。 （显然大O符号不是算法好坏的最终决定因素，我只是想确保我的理论在这里是正确的）。
这是一个很好的解决方案，还是 "original" 计数排序仍然可以做一些我看不到的高级事情？我也很好奇为什么 "hashmap-based counting sort" 几乎没有 returns 任何 Google 搜索结果，这让它看起来几乎没有被使用过。散列的开销是否足以超过其较小的内存占用？
你可以这样做，构造将是 O(n)，具有明显的内存优势。
有一个小问题。
要输出排序后的数组，您仍然需要对散列 table 键进行排序。而这个问题正是您首先要解决的问题。
不需要对key进行排序，作为key从min到max遍历即可
经典的计数排序示例要求您构建一个大小等于输入数组的最大整数的数组。
例如，如果您的数组是 [1, 6, 3, 10000, 8]，您需要一个长度为 10000 的数组来进行计数排序。
难道不能在同一线性时间内对整数使用散列 table 来完成吗？只是一张简单的地图？
在 python 中，它类似于：
counting_map = {n: 0 for n in input_array} # start by mapping all to 0
for num in input_array:
counting_map[n] += 1
我知道这真的只适用于整数，但在那种情况下映射解决方案不是更好吗？
在时间复杂度方面，您在 O(n) 时间内初始化映射，然后在 O(n) 时间内遍历数组，然后在 O(1) 时间内对输入执行哈希函数。 （显然大O符号不是算法好坏的最终决定因素，我只是想确保我的理论在这里是正确的）。
这是一个很好的解决方案，还是 "original" 计数排序仍然可以做一些我看不到的高级事情？我也很好奇为什么 "hashmap-based counting sort" 几乎没有 returns 任何 Google 搜索结果，这让它看起来几乎没有被使用过。散列的开销是否足以超过其较小的内存占用？
你可以这样做，构造将是 O(n)，具有明显的内存优势。
有一个小问题。
要输出排序后的数组，您仍然需要对散列 table 键进行排序。而这个问题正是您首先要解决的问题。
不需要对key进行排序，作为key从min到max遍历即可