JavaScript中如何按epoch时间戳对对象数组做高效降序排序

原实现的问题 #

你最初写的逻辑存在三个明显缺陷：

• 性能差：先后做了2次全量map遍历、1次reverse遍历，最后还对每个元素做find查找，整体时间复杂度为O(n²)，数据量超过千条时性能下降非常明显
• 有逻辑bug：如果存在两条及以上记录的transactionTime值相同，find只会返回第一条匹配的对象，会导致最终结果出现重复数据、丢失原记录
• 冗余操作多：先提取时间戳排序、再反查原对象的流程完全没有必要

全量数据排序的最优实现（99%场景适用） #

如果已经拿到API返回的全量数据，完全不需要使用优先队列，直接调用JavaScript原生Array.sort传入比较函数即可，整体时间复杂度O(nlogn)，没有冗余遍历，也不会出现同时间戳匹配错误的问题：

// 直接对数组按transactionTime降序排序，最新的记录排在最前
// 加[...data]是为了浅拷贝原数组，避免sort修改原数组，如果允许修改原数组可以去掉
const sortedData = [...data].sort((prev, curr) => curr.transactionTime - prev.transactionTime);

这个写法的优势：

• 没有多余的中间转换、回查步骤，排序时直接对比两个对象的时间字段，逻辑直接
• 性能远高于原实现，处理十万条级别的数据也不会有明显卡顿
• 代码可读性极强，其他开发者看到代码可以立刻理解排序规则

优先队列的适用场景 #

优先队列只适合流式接收数据、不需要全量排序、只需要动态获取Top N条最新记录的场景。如果已经拿到全量数据需要整体排序，用优先队列属于过度设计，性能反而不如原生的sort方法。
如果是流式数据场景，可以用最小堆实现的优先队列来维护需要的最新N条记录，参考代码如下：

// 最小堆实现的优先队列
class MinHeapPriorityQueue {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return top;
  }

  peek() {
    return this.heap[0];
  }

  get size() {
    return this.heap.length;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.heap[index], this.heap[parentIndex]) >= 0) break;
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  sinkDown(index) {
    const length = this.heap.length;
    while (true) {
      const leftIndex = 2 * index + 1;
      const rightIndex = 2 * index + 2;
      let smallest = index;
      if (leftIndex < length && this.compare(this.heap[leftIndex], this.heap[smallest]) < 0) {
        smallest = leftIndex;
      }
      if (rightIndex < length && this.compare(this.heap[rightIndex], this.heap[smallest]) < 0) {
        smallest = rightIndex;
      }
      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

// 用法示例：动态获取最新的10条交易记录
const LATEST_COUNT = 10;
const timeQueue = new MinHeapPriorityQueue((a, b) => a.transactionTime - b.transactionTime);

// 流式接收数据时逐条入队
for (const record of dataStream) {
  timeQueue.push(record);
  // 队列长度超过需要的数量时，弹出时间最早的记录
  if (timeQueue.size > LATEST_COUNT) {
    timeQueue.pop();
  }
}
// 最终队列内留存的就是时间最新的10条记录，出队反转后即可得到降序排列的结果

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