使用一次更新对有序列表中的元素重新排序

Reorder an element in an ordered list with a single update

本文关键字：元素 新排序 排序 列表 一次 更新      更新时间：2023-09-26

>假设我有一个列表，该列表按其元素的priority属性排序，这是一个数字。我知道列表中每个成员的priority值，但我想将一个元素移动到特定索引。是否可以仅通过修改要移动的元素的priority来做到这一点？

priority不需要是整数。任何算法都可用于确定元素的priority需要是什么，但priority必须是唯一的。

我认为获取所需索引之前和之后的元素priority，但我不知道如何在它们之间选择一个最终不会导致重复的数字。如果我只是在前面的元素中添加一些给定的值（整数或十进制），我最终会得到与后面的元素相同的值。在两者之间调用random()范围是可行的，但这似乎是一种非常迂回的做事方式。

如果这种操作有名字，我也有兴趣学习它。

值 m = （upper+lower）/2 总是在两个值的中间。

有关编号的进一步阅读，请参阅讲座：http://www.cs.uni-paderborn.de/fachgebiete/ag-boettcher/lehre/ss2012/dbis-2/download.html

（上+下）/2呢？

稍微扩展一下@msander的答案，您可以使用字母数字优先级来确保您始终具有要分配的"中间"优先级。如果您需要分配许多优先级，则两个连续优先级之间的距离将越来越低，最终将失去精度，并且您将得到类似（（上+下）/2 ===下）。

如果您更改获得中间优先级的方式，则可以使用字符串而不是实际数字（不会损失精度）。例如，如果您的优先级是类似字符串的数字（由 0,1,2,3,4,5,6,7,8,9 组成的字符串）：

["1"、"3"、"4"]

在 1 和 3 之间移动 4 将导致：["1"、"2"、"3"]

在 2 和 1 之间移动 3 将导致：["1"、"15"、"2"]

在 1 和 15 之间移动 2 将导致：["1"、"12"、"15"]

你需要注意的只是如何比较优先级（String.prototype.localeCompare）。

同样，只有当您预计会遇到精度损失的麻烦时，此解决方案才值得麻烦。

编辑（添加了一个计算优先级的函数）：

免责声明：代码出乎意料地难以遵循。如果有人有更好的主意，请随时加入。如果只使用二进制字符串（仅包含 0 和 1 的字符串），则编写起来会容易得多。

function getMiddlePriority(p1, p2) {
  var i=0,result = '';
  // The identical digits need to be in the result
  while ((p1[i] || '0') === (p2[i] || '0')) {
    result += p1[i++] || '0';
  }
  // First different digit p1[i] !== p2[i]
  // if the digits are far enough apart, there is a number between them
  if ((p2[i]||0) - (p1[i]||0) > 1) {
    return result + Math.floor(((+p2[i]||0) + (+p1[i]||0))/2);
  }
  // p2[i] === p1[i]+1
  // Digits are close, need to parse some more digits to get a number between
  var first = i++;
  var k = 0;
  while ((p1[i] === '9') && ((p2[i]||'0') === '0')) {
    i++; 
    k++;
  }

  // p[i] is not 9 or p2[i] is not 0/undefined
  if (p1[i] === '9') {
    result += (p2[first]||'0')  + repeat('0', k);
    result += p2[i] === '1' ? '05' : Math.floor(p2[i]/2);
  } else {
    result += (p1[first]||'0') + repeat('9', k);
    result += Math.floor((10 + (+p1[i] || 0))/2);
  } 
  return result;
}

function repeat(character, count) {
  var s = '';
  while (count--) s+= character;
  return s;
}

console.clear();
console.log('Expected 2 Got ' + getMiddlePriority('1', '3'));
console.log('Expected 25 Got ' + getMiddlePriority('2', '3'));
console.log('Expected 22 Got ' + getMiddlePriority('2', '25'));
console.log('Expected 21 Got ' + getMiddlePriority('2', '22'));
console.log('Expected 205 Got ' + getMiddlePriority('2', '21'));
console.log('Expected 202 Got ' + getMiddlePriority('2', '205'));
console.log('Expected 215 Got ' + getMiddlePriority('21', '22'));
console.log('Expected 1055 Got ' + getMiddlePriority('105', '106'));
console.log('Expected 10995 Got ' + getMiddlePriority('1099', '11'));
console.log('Expected 1105 Got ' + getMiddlePriority('1099', '111'));

字符串优先级的替代方法是使用数字优先级，并且每隔一段时间（(upper+lower)/2 === lower || (upper+lower)/2 === upper时）重新分配优先级。当然，这不符合这个问题，因为对于 N 次重新排序，您不会执行 1 次更新，而是1+ N/S更新，其中 S 是在可用优先级用完之前可以执行的更新量。至少这是一个正确的解决方案（优先级始终是唯一的）。

相关文章：