基于属性的对象数组交替排序的有效方法

Question

假设我们有一个对象数组，其中一个属性称为 cat。我们如何根据 cat 属性的值以一种高效且更简洁的方式对这个数组进行交替排序？假设类别值总是 'a' 或 'b'.

给定：

[
    {cat: 'a'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'a'},
    {cat: 'b'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'a'}
]

预期输出：

[
  { cat: 'a' },
  { cat: 'b' },
  { cat: 'a' },
  { cat: 'b' },
  { cat: 'a' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b' }
]

我实现了下面的解决方案，但是看起来很奇怪：

let myArr = [
  {cat: 'a'}, {cat: 'b'},
  {cat: 'b'}, {cat: 'a'},
  {cat: 'b'}, {cat: 'b'},
  {cat: 'b'}, {cat: 'b'},
  {cat: 'b'}, {cat: 'a'}
]

alternatedSort = (it, i, arr) => {
  function findAlternatedValueIndex(lookupIndex, it, arr){
    if(lookupIndex < arr.length && arr[lookupIndex].cat == it['cat']){
      lookupIndex ++
      return findAlternatedValueIndex(lookupIndex, it, arr)
    }
    else 
      return lookupIndex < arr.length ? lookupIndex : undefined
  }

  var lookupIndex = i + 1

  if (lookupIndex < arr.length && arr[lookupIndex].cat == it['cat']){
    let tgtIndex = findAlternatedValueIndex(lookupIndex, it, arr)
    if (tgtIndex) {
      const aux = arr[lookupIndex]
      arr[lookupIndex] = arr[tgtIndex]
      arr[tgtIndex] = aux
    }
  }
}

myArr.forEach(function(it, i, arr) {
  alternatedSort(it,i, arr)
});


console.log("sorted array: ", myArr)

obs：上面算法的复杂度是多少，我们能得到的最佳复杂度是多少？

Answer 1

'use strict'

catObjectArray = [
    {cat: 'a'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'a'},
    {cat: 'b'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'a'}
]

catObjectsByType = {
    'a': catObjectArray.filter(object =>  object.cat === 'a').length,
    'b': catObjectArray.filter(object =>  object.cat === 'b').length
}

let totalCatObjects = catObjectsByType.a + catObjectsByType.b

let sortedArrayOfCats = []

while (totalCatObjects !== 0){
    if(catObjectsByType.a > 0){
        if(totalCatObjects % 2 === 0){
            sortedArrayOfCats.push({cat: 'a'})
            catObjectsByType.a = catObjectsByType.a - 1
        } else {
            if(catObjectsByType.b > 0){
                sortedArrayOfCats.push({cat: 'b'})
                catObjectsByType.b = catObjectsByType.b - 1
            } else {
                sortedArrayOfCats.push({cat: 'a'})
                catObjectsByType.a = catObjectsByType.a - 1 
            }
        }
        totalCatObjects -= 1

    } else {
        sortedArrayOfCats.push({cat: 'b'})
        catObjectsByType.b = catObjectsByType.b - 1
        totalCatObjects -= 1
    }
}

console.log(sortedArrayOfCats)
/*
(10) [{…}, {…}, {…}, {…}, {…}, {…}, {…}, {…}, {…}, {…}]
0: {cat: "a"}
1: {cat: "b"}
2: {cat: "a"}
3: {cat: "b"}
4: {cat: "a"}
5: {cat: "b"}
6: {cat: "b"}
7: {cat: "b"}
8: {cat: "b"}
9: {cat: "b"}
*/

Answer 2

我只是将数组按 cat 拆分，然后交替合并结果。

let cata = arr.filter(x=> x.cat === 'a');
let catb = arr.filter(x=> x.cat === 'b');

let newarr =[];
let i = 0;

while (cata[i] || catb[i]) {
  if (cata[i]) newarr.push(cata[i]);
  if (catb[i]) newarr.push(catb[i]);
  i++;
}

这是在 O(n) 中，因为它只是数组的 3 次迭代。 O(n) 是你能得到的最好的，因为你必须至少查看数组中的每个元素一次。

另一种方法不需要预先拆分数组。它总共需要遍历数组2次（每个类别一次）并在遍历时填充新数组。

let newarr = [];
let a = 0, b = 0;
while (arr[a] || arr[b]) {
  while (arr[a]?.cat === 'b') a++;
  while (arr[b]?.cat === 'a') b++;
  
  if (arr[a])
    newarr.push(arr[a++])
  
  if (arr[b])
    newarr.push(arr[b++])
}

一种完全不同的方法，使用内置 Array.sort 就地执行（但以额外的属性为代价）可能是以下

分配给每个元素，如果它是其类别的第一个、第二个...。然后按 order 属性排序。如果两个元素具有相同的order，则在b

之前排序a

let a=0, b=0;
for (let e of arr) {
  e.order = e.cat === 'a' ? a++ : b++
}

arr.sort((x,y) => { 
  if (x.order === y.order) 
    return x.cat === 'a' ? -1 : +1;
  return x.order - y.order;
})

当然这至少是O(n logn)，取决于JS引擎使用的排序算法

Answer 3

这就是我解决这个问题的方法。虽然它不是最有效的，但它很可能足够有效，并且它是适用于任意数量密钥的通用方法。这个概念的变体在 SQL 查询中相对常见。

步骤是这样的：

为每个项目生成一个元组 [key, rank(key), item]。这里的 rank(key) 表示该键相对于其他具有相同值的键出现的序数。 rank不能有空隙：即'a'有1..3个ranks，'b'有1..6个ranks，'c'.[=46有1个ranks =]
按 rank(key) 排序元组，然后 key。
提取原始 item 值。

这里是广义的概念JavaScript。有一些库可以进一步抽象这种方法。

最初，给定不同组中的一些项目：

var items = [
    { cat: 'a', name: 'first a' },
    { cat: 'b', name: 'first b' },
    { cat: 'b' },
    { cat: 'a' },
    { cat: 'b' },
    { cat: 'b' },
    { cat: 'c', name: 'Mr. C' },
    { cat: 'b' },
    { cat: 'b', name: 'last b' },
    { cat: 'a', name: 'last a' }
]

获取项目并构建一个元组序列，其中包含每次出现的键的排名。这是一个 O(n) 操作。

var ranks = {}; // key -> last rank (undefined = 0)
var t = [];

for (let i of items) {
  var rk = (ranks[i.cat] = (ranks[i.cat] || 0) + 1);
  t.push([i.cat, rk, i]); 
}

现在t如下。（键的重复在这里是为了解释这个概念，以及更通用的排序，尽管排序可以很好地访问原始对象，从而消除元组索引。同样，可以将原始对象突变为包含排名。)

[
  [ 'a', 1, { cat: 'a', name: 'first a' } ],
  [ 'b', 1, { cat: 'b', name: 'first b' } ],
  [ 'b', 2, { cat: 'b' } ],
  [ 'a', 2, { cat: 'a' } ],
  [ 'b', 3, { cat: 'b' } ],
  [ 'b', 4, { cat: 'b' } ],
  [ 'c', 1, { cat: 'c', name: 'Mr. C' }, ],
  [ 'b', 5, { cat: 'b' } ],
  [ 'b', 6, { cat: 'b', name: 'last b' } ],
  [ 'a', 3, { cat: 'a', name: 'last a' } ]
]

接下来，按排名排序，然后按关键字排序。这种通用排序操作是 O(n lg n)，使其成为算法的大 O。

t.sort((a, b) => (a[1] - b[1]) || a[0].localeCompare(b[0]));

排序后t为：

[
  [ 'a', 1, { cat: 'a', name: 'first a' } ],
  [ 'b', 1, { cat: 'b', name: 'first b' } ],
  [ 'c', 1, { cat: 'c', name: 'Mr. C' } ],
  [ 'a', 2, { cat: 'a' } ],
  [ 'b', 2, { cat: 'b' } ],
  [ 'a', 3, { cat: 'a', name: 'last a' } ],
  [ 'b', 3, { cat: 'b' } ],
  [ 'b', 4, { cat: 'b' } ],
  [ 'b', 5, { cat: 'b' } ],
  [ 'b', 6, { cat: 'b', name: 'last b' } ]
]

最后，遍历元组并提取与原始对象对应的第三个元素。这是 O(n).

var interwovenItems = t.map(x => x[2]);

产生最终结果：

[
  { cat: 'a', name: 'first a' },
  { cat: 'b', name: 'first b' },
  { cat: 'c', name: 'Mr. C' },
  { cat: 'a' },
  { cat: 'b' },
  { cat: 'a', name: 'last a' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b', name: 'last b' }
]

Answer 4

另一种方法是更通用。如果我们有类别 A、B、C 和 D 并想按顺序循环它们怎么办？如果密钥位于属性与 cat 不同的位置怎么办？

此解决方案在两个更通用的助手之上编写了一个简单的函数。第一个 group 与 groupBy functions found in many libraries 类似，只是它 returns 不是返回一个对象，而是一个数组他们产生。通过对结果调用 Object.values，可以很容易地在其中一个之上构建它。

第二个助手 seqMerge 获取一组数组并通过按顺序从每个数组中选取第一个值，然后从每个数组中选取第二个值等来重新排列它们，只需在每个数组为空时跳过它。看起来像这样：

seqMerge ([
  [1, 11], 
  [2, 22, 32, 42, 52, 62], 
  [3, 13, 33]
])
//=> [1, 2, 3, 11, 22, 13, 32, 33, 42, 52, 62]

有了这些，我们的主要功能就变得微不足道了：

const group = (fn) => (xs) => 
  Object .values (
    xs .reduce ((a, x) => ({...a, [fn (x)]: [... (a [fn (x)] || []), x]}), {})
  )

const seqMerge = ([[x = undefined, ...xs], ...xss]) => 
  x == undefined 
    ? xss .length == 0 ? [] : seqMerge (xss)
    : [x, ... seqMerge ([...xss, xs])]


const alternatingSort = (keyGen) => (xs) => 
  seqMerge (group (keyGen) (xs))

const xs = [{cat: 'a', id: 1}, {cat: 'b', id: 2}, {cat: 'b', id: 3}, {cat: 'a', id: 4}, {cat: 'b', id: 5}, {cat: 'b', id: 6}, {cat: 'b', id: 7}, {cat: 'b', id: 8}, {cat: 'b', id: 9}, {cat: 'a', id: 10}]

console .log (alternatingSort (x => x .cat) (xs))

.as-console-wrapper {max-height: 100% !important; top: 0}

请注意，此版本允许我们喜欢多少类别，而不仅仅是两个。它允许我们决定使用不同的属性来对值进行分区，甚至允许我们为此创建一个合成键。但是使用还是很简单的。

扩展程序

我们可能想通过多种方式来扩展它。可能有理由对我们要产生的组进行排序。那只是意味着做这样的事情：

const alternatingSort = (keyGen) => (xs) => 
  seqMerge (
    group (keyGen) (xs) 
      .sort (([a], [b], x = keyGen (a), y = keyGen (b)) => x < y ? -1 : x > y ? 1 : 0)
  )

或者我们可能会注意到 Rich Snapp 所谓的 Reduce ({...spread}) antipattern，并决定用

以一种不太优雅但更有效的方式修复 group

const group = (fn) => (xs) => 
  Object .values (xs .reduce (
    (a, x, _, __, k = fn (x)) => ((a [k] = a [k] || []), (a [k] .push (x)), a),
    {}
  ))

或同一想法的更命令式版本。

而且，在我们讨论性能时，我们可能希望更仔细地研究 seqMerge。我发现该代码优雅且非常漂亮。但是当组合列表长度接近递归深度限制时它会触底，并且很可能在此之前很久就表现得很糟糕。如果您将它用于几十个长的列表，那么这将不是问题。

我们可以在 transpose 函数之上重写它。但它不能是任何旧的转置。例如，我的默认版本 (xs) => xs [0] .map ((_, i) => xs .map (r => r[i])) 在这里不起作用。 transpose 顺便说一下，在其主对角线上翻转一个矩形网格。例如：

transpose ([
  [1, 2, 3,  4,  5],
  [2, 3, 5,  7, 11],
  [1, 4, 9, 16, 25]
]) //=> 
// [
//   [1, 2, 1], 
//   [2, 3, 4], 
//   [3, 5, 9], 
//   [4, 7, 16], 
//   [5, 11, 25]
// ]

但参差不齐的网格上的行为未定义。对于这个问题，我们希望包括所有结果，即使列的长度不同也是如此。我们可以编写一个这样的版本：

const transpose = (xs) => Array .from (
  {length: Math .max (... xs .map (r => r .length))}, 
  (_, i) => xs .map (r => r [i]) .filter ((x => x != null))
)

然后我们的顺序合并函数很简单：

const seqMerge = (xs) => 
  transpose (xs) .flat ()

基于属性的对象数组交替排序的有效方法

Efficient way of alternating sort of array of objects based on property

javascript

algorithm

sorting

time-complexity

coding-efficiency

扩展程序

基于 属性 的对象数组交替排序的有效方法

Efficient way of alternating sort of array of objects based on property

javascript

algorithm

sorting

time-complexity

coding-efficiency

扩展程序

基于属性的对象数组交替排序的有效方法