自行构思的排序算法叫什么名称？性能表现怎么样？

问题1解答 #

你不是第一个想到这个算法的人，它的官方名称是计数排序（Counting Sort），你当前写的是仅支持非负整数、不支持重复元素的简化实现版本。

问题2解答 #

它看起来高效但应用场景有限，核心存在几个明显的局限性：

• 空间成本过高：该算法的空间占用完全由待排序数组的最大值决定，和数组本身的长度无关。举个例子，如果你要排序的数组是[1, 9999999]，你需要创建长度接近1000万的布尔数组，仅仅为了排序2个元素，空间浪费极其严重，甚至会直接触发内存不足的问题。
• 输入限制非常多：首先只能处理非负整数，元素值不能为负（负数作为数组下标直接越界），也不能处理浮点数、字符串等其他需要排序的常见数据类型，通用性极差。
• 你当前的实现不支持重复元素：你用布尔数组标记的逻辑，遇到多个重复值的情况会直接丢失数据，比如输入[2,2,3]，排序后只会输出[2,3]，不符合排序要求。就算你把布尔数组换成整型计数数组解决重复问题，前面的空间和输入限制问题依然存在。
• 时间复杂度优势只在特定场景成立：你觉得它效率高是因为它的时间复杂度是O(n + k)，其中n是数组长度，k是数组元素的最大值。只有当k远小于n的时候，它的效率才会高于快速排序、归并排序这类O(nlogn)的通用排序算法；如果k远大于n，它的运行效率反而会比通用排序低很多。

当然这个算法也不是完全没有应用，当待排序的元素都是整数、且取值范围非常窄的时候，比如给满分100分的考试成绩排序、给人群的年龄排序，这类场景下计数排序的效率要远高于通用排序算法，会被频繁使用。

内容的提问来源于stack exchange，提问作者user14587078