JavaScript按元素频率排序数组：字符串正常数字数组失效如何解决

问题根因 #

• 你当前的排序逻辑仅对比了元素的出现频率，当两个元素的出现频率相等时，没有定义额外的排序规则，JavaScript 内置的sort方法在这种场景下的排序结果是不稳定的，直接导致同频率的元素顺序出现随机错乱，这就是数字数组排序结果不符合预期的核心原因。
• 额外性能问题：当前统计元素频率的逻辑会在遍历每个元素时全量遍历整个数组计数，时间复杂度为O(n²)，数组长度较大时性能损耗非常明显，可优化为单次遍历完成频率统计。

修复后的代码 #

版本1：同频率按元素值大小升序排列 #

function frequencySort(arr){
  // 单次遍历统计频率，时间复杂度降为O(n)
  const freq = {}
  arr.forEach(item => {
    freq[item] = (freq[item] || 0) + 1
  })
  arr.sort(function(a,b){
    const freqDiff = freq[b] - freq[a]
    // 频率相同时按元素值升序，可根据需求调整为b - a实现降序
    return freqDiff === 0 ? a - b : freqDiff
  })
  return arr
}

调用frequencySort([4, 6, 2, 2, 6, 4, 4, 4])将返回[4, 4, 4, 4, 2, 2, 6, 6]

版本2：同频率按元素在原数组的首次出现顺序排列 #

如果需要同频率元素保持原数组中的相对出现顺序，可额外存储元素首次出现的索引做排序判断：

function frequencySort(arr){
  const freq = {}
  const firstOccurIndex = {}
  arr.forEach((item, index) => {
    if (freq[item] === undefined) {
      freq[item] = 0
      firstOccurIndex[item] = index
    }
    freq[item]++
  })
  arr.sort(function(a,b){
    const freqDiff = freq[b] - freq[a]
    // 频率相同时按首次出现索引升序，保持原出现顺序
    return freqDiff === 0 ? firstOccurIndex[a] - firstOccurIndex[b] : freqDiff
  })
  return arr
}

调用frequencySort([4, 6, 2, 2, 6, 4, 4, 4])将返回[4, 4, 4, 4, 6, 6, 2, 2]

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