基于cat属性实现对象数组交替排序的高效方案与复杂度分析

1. 原算法时间复杂度 #

• 最坏时间复杂度为 O(n²)：外层遍历数组每个元素的开销是O(n)，当遇到连续相同cat属性的元素时，需要向后递归查找不同分类的元素，最坏情况（如数组前半段全为a、后半段全为b）每次查找需要遍历O(n)个元素，整体复杂度叠加为O(n²)。
• 最坏空间复杂度为 O(n)：递归查找的调用栈最坏深度可达O(n)。

2. 场景最优时间复杂度 #

该场景的最优时间复杂度为 O(n)，仅需遍历数组2次即可完成排序，性能远优于原实现。

最简实现示例（O(n)时间 + O(n)空间） #

思路是先拆分两类元素，再按规则交替拼接：

const alternateSort = (arr) => {
  // 一次遍历拆分两类元素
  const as = arr.filter(item => item.cat === 'a')
  const bs = arr.filter(item => item.cat === 'b')
  const res = []
  const minLen = Math.min(as.length, bs.length)
  // 交替拼接
  for(let i = 0; i < minLen; i++){
    res.push(as[i], bs[i])
  }
  // 追加剩余元素
  return res.concat(as.slice(minLen), bs.slice(minLen))
}

// 测试
const myArr = [
  {cat: 'a'}, {cat: 'b'},
  {cat: 'b'}, {cat: 'a'},
  {cat: 'b'}, {cat: 'b'},
  {cat: 'b'}, {cat: 'b'},
  {cat: 'b'}, {cat: 'a'}
]
console.log(alternateSort(myArr)) // 完全匹配预期输出

如果要求原地修改不额外占用空间，也可以用双指针法实现O(n)时间 + O(1)空间的方案。

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