如何在Clojure中用frequencies函数实现O(n)时间的整数计数排序？

完全没问题，用frequencies函数配合遍历取值范围的方式，刚好能实现你要的O(n)时间复杂度排序——这本质上就是计数排序的简化实现，非常适合元素取值范围已知且相对集中的整数数组。

具体步骤如下： #

1. 统计元素频率：先调用frequencies xs，得到一个以数组元素为键、出现次数为值的映射（比如哈希表或关联列表）。这个操作的时间复杂度是O(n)，因为需要遍历数组一次统计每个元素的出现次数。
2. 按范围生成有序数组：从0开始，依次遍历到max（注意要包含max这个边界值）：
   • 对每个整数x，查询频率映射中对应的次数count；如果x不在映射里（说明数组中没有这个元素），直接跳过。
   • 如果count大于0，就把x重复count次，依次追加到结果数组中。
3. 得到有序结果：遍历完成后，结果数组就是严格从小到大排好序的数组。

举个实际例子 #

假设你的数组是xs = [3,1,4,1,5,2,5,3,5]，max=5：

• 调用frequencies xs会得到类似{1:2, 2:1, 3:2, 4:1, 5:3}的映射
• 从0到5遍历：
  • 0：无频率，跳过
  • 1：次数2 → 追加[1,1]
  • 2：次数1 → 追加[2]
  • 3：次数2 → 追加[3,3]
  • 4：次数1 → 追加[4]
  • 5：次数3 → 追加[5,5,5]
• 最终得到排序后的数组：[1,1,2,3,3,4,5,5,5]

时间复杂度说明 #

这个方法的总时间复杂度是O(n + max)：

• frequencies操作是O(n)
• 遍历0到max是O(max)
  当max的数值远小于数组长度n时，整体复杂度就趋近于O(n)，完全满足你的要求。而如果直接用普通的sort xs，时间复杂度通常是O(n log n)，在元素范围小的场景下效率远不如这个方法。

内容的提问来源于stack exchange，提问作者R u c k s a c k