带偏置的数组排序：寻求替代现有简易实现的更优算法

需求说明 #

需要对类型为items: Array<{ totalScore: number }>的数组排序，支持两种调用方式：biasSort(items) 或 items.sort(biasSort)。核心要求是按totalScore降序排列的基础上，加入随机性偏置，让低分元素也有机会排到顶部。

现有简易实现 #

export const biasSort = (items: { totalScore: number }[]) => {
  // Step 1: Sort by descending total scores
  const sortedItems = [...items].sort((a, b) => b.totalScore - a.totalScore);

  // Step 2: Introduce randomness with probability inversely proportional to score difference
  const scores = sortedItems.map(({ totalScore }) => totalScore);
  const maxScoreDifference = Math.max(...scores) - Math.min(...scores);

  // Adjust positions based on probability inversely proportional to score difference
  return [...sortedItems].sort((a, b) => {
    const scoreDifference = b.totalScore - a.totalScore;
    const probability = 1 - scoreDifference / maxScoreDifference;

    // Adjust positions based on probability
    return Math.random() < probability ? 1 : -1;
  });
};

问题与优化方向 #

现有实现存在两个明显问题：

• 当所有元素分数相同时，maxScoreDifference为0，会触发除以0的错误；
• 两次排序的设计效率偏低，且概率逻辑的灵活性不足。

下面介绍两种成熟的算法方案，以及对原实现的修复：

1. 加权随机排序（高效生成结果） #

思路：直接基于元素分数作为权重，通过加权随机抽样的方式逐个选取元素，最终生成有序结果。分数越高的元素被优先选中的概率越大，但低分元素仍有机会提前入选。

export const biasSort = (items: { totalScore: number }[], weightPower = 1) => {
  const copy = [...items];
  const result: typeof items = [];

  while (copy.length > 0) {
    // 计算总权重：可通过weightPower调整偏置强度，值越大高分优先级越高
    const totalWeight = copy.reduce((sum, item) => sum + Math.pow(item.totalScore, weightPower), 0);
    let randomThreshold = Math.random() * totalWeight;

    // 找到对应阈值的元素并加入结果
    for (let i = 0; i < copy.length; i++) {
      randomThreshold -= Math.pow(copy[i].totalScore, weightPower);
      if (randomThreshold <= 0) {
        result.push(copy.splice(i, 1)[0]);
        break;
      }
    }
  }

  return result;
};

• 调整偏置：通过weightPower参数控制，比如设为2时高分元素的权重会被放大，随机性减弱；设为0.5时随机性增强。
• 优势：无需提前排序，一次遍历即可生成结果，效率更高。

2. 玻尔兹曼排序（灵活控制随机性） #

思路：模拟热力学玻尔兹曼分布，通过温度参数T控制随机程度：

• T趋近于0：接近严格降序排序；
• T越大：随机性越强，排序越接近完全随机；
• T取1左右：平衡排序规则与随机性。

适合直接作为Array.sort的比较器使用：

// 生成带温度参数的比较器
export const createBiasSortComparator = (temperature = 1) => {
  return (a: { totalScore: number }, b: { totalScore: number }) => {
    const scoreDelta = b.totalScore - a.totalScore;
    // 基于玻尔兹曼分布计算交换概率
    const swapProbability = 1 / (1 + Math.exp(-scoreDelta / temperature));
    return Math.random() < swapProbability ? -1 : 1;
  };
};

// 调用示例：
// items.sort(createBiasSortComparator(0.5)) // 偏严格降序
// items.sort(createBiasSortComparator(2))   // 偏随机

• 优势：符合原生sort调用规范，无需额外复制数组，且温度参数可灵活调整偏置程度。

原实现的修复版本 #

如果要保留原思路，需处理分数差为0的边界情况：

export const biasSort = (items: { totalScore: number }[]) => {
  const sortedItems = [...items].sort((a, b) => b.totalScore - a.totalScore);
  const scores = sortedItems.map(item => item.totalScore);
  const maxScore = Math.max(...scores);
  const minScore = Math.min(...scores);
  const maxScoreDifference = maxScore - minScore;

  return sortedItems.sort((a, b) => {
    // 所有元素分数相同时，随机排序
    if (maxScoreDifference === 0) {
      return Math.random() > 0.5 ? 1 : -1;
    }
    const scoreDifference = b.totalScore - a.totalScore;
    const probability = 1 - scoreDifference / maxScoreDifference;
    return Math.random() < probability ? 1 : -1;
  });
};

• 不足：仍需两次排序，效率不如前两种方案。

总结 #

• 追求灵活调参：优先选择玻尔兹曼排序的比较器方案；
• 追求高效生成结果：优先选择加权随机排序；
• 保留原逻辑：使用修复后的版本即可解决边界问题。

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