咨询：自定义排序算法是否已被发明？是否为O(n)线性时间复杂度？

你的排序实现代码：

const objSort = (arr) => { 
  let storage = {}; 
  let sorted = []; 
  let entries; 
  arr.forEach((num) => { 
    storage[num] ? storage[num]++ : storage[num] = 1; 
  }); 
  entries = Object.entries(storage); 
  entries.forEach(([ key, value ]) => { 
    for (let i = 0; i < value; i++) { 
      sorted.push(+key); 
    } 
  }); 
  return sorted; 
};

嘿，咱们来逐个解答你的两个技术疑问：

当然啦！这其实是**计数排序（Counting Sort）**的一种JavaScript实现变体。

计数排序是非常经典的线性时间排序算法，核心思路就是先统计每个元素的出现频率，再根据频率把元素按顺序还原成有序数组。传统的计数排序会用数组来存储频率，而你改用了JS对象来完成统计——本质逻辑完全一致，只是存储载体不同而已。所以这个算法思路早就被提出并广泛应用啦。

这个不能一概而论，得看输入场景：

符合计数排序适用条件时：是O(n) #

如果输入数组中的数字取值范围有限，且范围大小与数组长度n同阶（比如数组里全是0~100的整数，而n是1000），那时间复杂度确实是线性的：

• 第一步遍历数组统计频率：O(n)
• 第二步Object.entries(storage)遍历不同数字：O(k)，其中k是不同数字的数量，这里k是常数或O(n)
• 第三步根据频率填充结果数组：O(n)（所有数字的出现次数之和等于原数组长度n）
  总时间复杂度为O(n + k)，由于k≤n，所以等价于O(n)。

存在隐藏陷阱时：可能退化为O(n log n) #

你担心的“对象如何原生排序数字”是关键！在ES6+规范中，JS对象的**整数类型键（或可转换为整数的字符串键）**会被引擎自动按数值升序排列，但这个排序操作的时间复杂度是O(k log k)（k是不同数字的数量）。

如果输入数组中的数字取值范围极大且几乎没有重复（比如数组里是[1, 1000000, 999999, ...]，k≈n），那这一步的排序时间就会变成O(n log n)，总时间复杂度也就退化为O(n log n)，不再是线性时间了。

另外还要注意：如果输入的是带小数的数字（比如1.5），对象会把它们当作字符串键，按字符串字典序排序（比如"10.1"会排在"2"前面），这会导致排序结果错误，这也是你这个实现的局限性之一。

最后你提到空间表现很差，这点确实没错：如果输入数字的取值范围跨度极大，即使是用对象存储频率，空间开销也会很高，这是计数排序类算法的固有特性——空间换时间。

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