如何用jQuery按属性值排序高效插入新HTML列表项

因为列表本身始终保持毫秒时间戳升序的规则，完全不需要全量遍历元素比对，用二分查找可以把定位插入位置的时间复杂度降到O(log n)，哪怕是十万级、百万级的列表项，最多只需要20次以内的比对就能找到参考节点，性能损耗可以忽略。

具体实现方案 #

方案1：维护索引缓存（性能最优，推荐） #

• 首次加载列表时，同步生成一个和DOM顺序完全一致的时间戳缓存数组，避免后续反复读取DOM属性带来的开销：

// 初始化缓存
const messageList = document.querySelector('ul');
const tsCache = Array.from(messageList.querySelectorAll('li'))
  .map(item => Number(item.getAttribute('ts')));

• 新元素插入前，用二分查找在有序缓存数组里定位插入下标：

// 二分查找：返回第一个大于目标ts值的元素下标
function getInsertIndex(sortedArr, targetTs) {
  let left = 0, right = sortedArr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (sortedArr[mid] < targetTs) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
}

// 以示例中的新ts为例
const newTs = 1657744950123;
const insertIndex = getInsertIndex(tsCache, newTs);

• 执行插入并同步更新缓存：

// 构造新的li元素
const newItem = document.createElement('li');
newItem.setAttribute('ts', newTs);
newItem.textContent = 'New Item';

if (insertIndex === tsCache.length) {
  // 新元素时间最大，直接插在末尾
  messageList.append(newItem);
} else {
  // 找到对应下标的参考元素，在它之前插入新元素
  messageList.children[insertIndex].before(newItem);
}
// 同步更新缓存数组，保证后续查找顺序正确
tsCache.splice(insertIndex, 0, newTs);

如果用jQuery的话，把DOM操作部分换成对应jQuery语法即可，比如$(messageList.children[insertIndex]).before(newItem)。

方案2：直接对DOM子元素做二分查找（无需维护缓存） #

如果不想额外维护缓存数组，也可以直接对列表的子元素集合做二分查找，只是每次比对需要读取DOM的ts属性，性能比缓存方案稍差，但远快于全量遍历：

const $list = $('ul');
const newTs = 1657744950123;
const children = $list[0].children;
let left = 0, right = children.length;

while (left < right) {
  const mid = Math.floor((left + right) / 2);
  const midTs = Number(children[mid].getAttribute('ts'));
  if (midTs < newTs) {
    left = mid + 1;
  } else {
    right = mid;
  }
}

const $newItem = $('<li>', {ts: newTs, text: 'New Item'});
if (left === children.length) {
  $list.append($newItem);
} else {
  $(children[left]).before($newItem);
}

注意事项 #

• 以上方案成立的核心前提是列表始终保持ts升序，只要所有插入、删除操作都同步更新缓存（或直接操作DOM保证顺序），二分查找的有序条件就一直成立。
• 不要在每次插入前重新全量读取DOM生成缓存，会引入不必要的DOM查询开销，维护JS数组缓存的splice操作耗时极低，完全可以忽略。

内容的提问来源于stack exchange，提问作者Alexander M.