JavaScript按前序LocID属性值排序对象数组（保持d升序）

现有一个包含LocID和d属性的JavaScript对象数组，已按d属性升序排序：

var a = [
{'LocID':16660,d:0},
{'LocID':16654,d:22.9},
{'LocID':16660,d:22.9},
{'LocID':16650,d:37.83},
{'LocID':16654,d:37.83},
{'LocID':16650,d:63.5},
{'LocID':16655,d:63.5},
{'LocID':16660,d:70.0}
]

需求：在保持d属性升序的基础上，对数组进行二次排序，当d值相同时，使当前元素的LocID与前一个元素的LocID尽可能一致，让相同LocID的元素相邻；若LocID重复出现，需保持d的升序以区分。

期望排序结果：

[
{'LocID':16660,d:0},
{'LocID':16660,d:22.9},
{'LocID':16654,d:22.9},
{'LocID':16654,d:37.83},
{'LocID':16650,d:37.83},
{'LocID':16650,d:63.5},
{'LocID':16655,d:63.5},
{'LocID':16660,d:70.0}
]

原数组已经按d升序排列，我们不需要改动d的整体顺序，只需要调整相同d值元素的位置，尽量让相同LocID的元素相邻，同时保证同一LocID的元素d保持递增（这一点原数组已经满足，因为整体是按d升序排序的）。

可以通过遍历构建新数组的方式实现：

function reorderArray(arr) {
  if (arr.length === 0) return [];
  
  const result = [arr[0]];
  // 按LocID分组存储剩余未处理的元素
  const remaining = new Map();
  
  // 初始化分组
  for (let i = 1; i < arr.length; i++) {
    const item = arr[i];
    if (!remaining.has(item.LocID)) {
      remaining.set(item.LocID, []);
    }
    remaining.get(item.LocID).push(item);
  }
  
  // 逐步构建结果数组
  for (let i = 1; i < arr.length; i++) {
    const lastLocID = result[result.length - 1].LocID;
    // 优先选择和最后一个元素LocID相同的剩余元素
    if (remaining.has(lastLocID) && remaining.get(lastLocID).length > 0) {
      result.push(remaining.get(lastLocID).shift());
    } else {
      // 没有相同LocID的元素时，取任意有剩余元素的分组的第一个元素
      for (const [key, items] of remaining) {
        if (items.length > 0) {
          result.push(items.shift());
          break;
        }
      }
    }
  }
  
  return result;
}

// 测试示例
var a = [
{'LocID':16660,d:0},
{'LocID':16654,d:22.9},
{'LocID':16660,d:22.9},
{'LocID':16650,d:37.83},
{'LocID':16654,d:37.83},
{'LocID':16650,d:63.5},
{'LocID':16655,d:63.5},
{'LocID':16660,d:70.0}
];

console.log(reorderArray(a));

思路拆解 #

1. 先把数组的第一个元素放入结果数组，作为排序的起始项。
2. 将剩余元素按LocID分组存储，这样可以快速定位到同LocID的待处理元素。
3. 每次向结果数组添加元素时，优先选择和结果数组最后一个元素LocID相同的剩余元素，以此保证相同LocID的元素相邻。
4. 如果没有同LocID的剩余元素，就从任意还有未处理元素的分组中取第一个元素补上。
5. 由于原数组已经按d升序排序，同一LocID的元素在分组中也是按d递增排列的，直接取分组的第一个元素就能保证d的升序要求不被破坏。

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