在一个数组中对非连续元素进行排序

Question

我有一个项目列表，想要按照字段enqueuedAt降序排序。在属于同一队列（由queueName标识）的项目中，position（最低优先级）应优先于enqueuedAt。

换句话说，总排序顺序应基于enqueuedAt（降序），在其中，属于同一队列的项目应相互交换位置，以便具有较低position的项目始终出现在具有较高position的项目之前。

我为了实现这个目标编写了下面的代码。 有没有方法可以提高时间复杂度？

const data = [
  {
    id: 1,
    enqueuedAt: 8,
    queueName: 'Queue 1',
    position: 1
  },
  {
    id: 2,
    enqueuedAt: 7,
    queueName: 'Queue 2',
    position: 1
  },
  {
    id: 3,
    enqueuedAt: 6,
    queueName: 'Queue 3',
    position: 3
  },
  {
    id: 4,
    enqueuedAt: 5,
    queueName: 'Queue 4',
    position: 2
  },
  {
    id: 5,
    enqueuedAt: 1,
    queueName: 'Queue 1',
    position: 2
  },
  {
    id: 6,
    enqueuedAt: 2,
    queueName: 'Queue 4',
    position: 1
  },
  {
    id: 7,
    enqueuedAt: 4,
    queueName: 'Queue 1',
    position: 3
  },
  {
    id: 8,
    enqueuedAt: 3,
    queueName: 'Queue 2',
    position: 2
  }
]

function sortThem(array) {
  array.sort((a, b) => b.enqueuedAt - a.enqueuedAt)

  for (let i = 0; i < array.length - 1; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i].queueName === array[j].queueName) {
        if (array[j].position < array[i].position) {
          const t = array[j]
          array[j] = array[i]
          array[i] = t
        }
      }
    }
  }

  return array
}

console.log(sortThem(data))

- karthikaruna

---

“enqueuedAt”是否保证唯一？ - trincot

是的，它保证是唯一的。 - karthikaruna

为什么 enqueuedAt 为3的条目没有排在 enqueuedAt 为2的前面？ - trincot

因为根据 enqueuedTime 进行排序后，你所说的那个项目（具有 enqueuedAt 2 的项目）的位置（索引3）属于队列4。不允许将属于另一个队列的某些项目放在那里。只有属于队列4的项目可以去那里，前提是它的 position 小于原占用者的 position。 - karthikaruna

“某些属于另一个队列的项目不允许进入那里”：我不理解这个规则，也没有在你的问题中看到这个规则。我只看到两个规则：（1）当它不与规则2冲突时，顺序应按照降序的enqueuedTime；（2）来自同一队列的项目应按其位置保持顺序。似乎您在这里有一个未写下的第三条规则，涉及属于某些队列的位置。我发布了一个答案，遵循我在您的问题中找到的两个规则。但是它会给出不同的输出，因为它不知道这个第三个规则。 - trincot

Answer 1

我认为你的代码没有正确地优先考虑 queuedAt，你的算法首先按 queuedAt 排序，然后交换出现在错误位置顺序的元素，但这并不总是会得到一个优先考虑 queuedAt 的顺序。

例如，在你的输出中，queuedAt=3 的元素出现在 queuedAt=2 的元素之后，然而它们也可以按相反的顺序出现：经过适当的排序仍然可以按其位置顺序列出项目，但会优先考虑更大的 queuedAt 值。

建议的算法如下：

为了纠正这个缺点，以及获得更好的时间复杂度，您可以使用最大堆heap。堆中的一个条目对应于一个队列，其中所有元素都按position排序。堆要使用的key将是队列第一个元素的queuedAt属性，即具有最小position值的属性。

然后，您将从堆中选择顶部条目（队列），提取该队列的第一个元素，并将其推送到最终结果。如果队列还没有空，那么将其留在堆中，但调整其key，使其再次对应于现在排在第一位（最小position）的队列元素的queuedAt属性。如果队列用尽，则将其从堆中删除。如果您继续这样做，直到堆被清空，您将按所需顺序访问条目。

很遗憾，JavaScript没有本地堆实现。因此，您需要自己编写或包含库（有几个库可供选择）。我将在此处包含我在Efficient way to implement Priority Queue in Javascript?中回答的实现的缩小版本。请参见该代码的解释。

在下面的实现中，我选择以相反的顺序对队列进行排序，以便可以按所需顺序pop元素。

我们开始吧：

/* MinHeap minimised - taken from https://dev59.com/tFgQ5IYBdhLWcg3wWCg0#66511107 */
const MaxHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]<h[j+1][0])j++;if(j>=h.length||k>=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k>h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};

// Main function
function customSort(data) {
  // Create a map with a key for each queue
  let map = new Map(data.map(o => [o.queueName, []]));
  // Populate the map entries
  for (let o of data) map.get(o.queueName).push(o);
  // We have no more need of the Map:
  let queues = [...map.values()];
  // Sort each queue by descending position (so we can pop from those queues in ascending order)
  for (let queue of queues) queue.sort((a, b) => b.position - a.position);

  // Build a heap of pairs, where first value in pair is the heap key, and the second is the payload (the queue)
  let heap = MaxHeap.heapify(queues.map(queue => [queue[queue.length - 1].enqueuedAt, queue]));

  let result = [];
  while (heap.length) {
    // Peek in the heap, to get the "top" queue
    let queue = heap[0][1];
    // Extract the element from that queue with the lowest position
    result.push(queue.pop());
    if (queue.length) {
      // Adapt the key of this queue on the heap
      MaxHeap.exchange(heap, [queue[queue.length - 1].enqueuedAt, queue]);
    } else {
      // Remove the now empty queue from the heap
      MaxHeap.pop(heap);
    }
  }
  return result;
}

// Example data from the question:
const data = [{id: 1,enqueuedAt: 8,queueName: 'Queue 1',position: 1},{id: 2,enqueuedAt: 7,queueName: 'Queue 2',position: 1},{id: 3,enqueuedAt: 6,queueName: 'Queue 3',position: 3},{id: 4,enqueuedAt: 5,queueName: 'Queue 4',position: 2},{id: 5,enqueuedAt: 1,queueName: 'Queue 1',position: 2},{id: 6,enqueuedAt: 2,queueName: 'Queue 4',position: 1},{id: 7,enqueuedAt: 4,queueName: 'Queue 1',position: 3},{id: 8,enqueuedAt: 3,queueName: 'Queue 2',position: 2}]

console.log(customSort(data));

时间复杂度是O(nlogn)，类似于基于比较的排序算法。

无需堆的解决方案

在JavaScript中，可以不使用堆来实现此功能，但需要限制requiredAt的范围（但仍然是一个大的范围：2³²）：我们可以利用JavaScript对普通对象保证的键迭代顺序，自2017-2020年更新的语言规范以来。

在堆中，requiredAt是键，它可以变成普通对象中的键。由于需要将顺序设置为降序，因此必须将requiredAt映射到可以按升序迭代的正整数。映射可以是32000 - requiredAt之类的内容。

以下是如何编写代码：

function customSort(data) {
  // Create a map with a key for each queue
  let map = new Map(data.map(o => [o.queueName, []]));
  // Populate the map entries
  for (let o of data) map.get(o.queueName).push(o);
  // We have no more need of the Map:
  let queues = [...map.values()];
  // Sort each queue by descending position (so we can pop from those queues in ascending order)
  for (let queue of queues) queue.sort((a, b) => b.position - a.position);

  // Build an object keyed by "negative" `queuedAt`
  const MAX = 2 ** 31 - 1;
  let sorted = Object.fromEntries(queues.map(queue => [MAX - queue[queue.length - 1].enqueuedAt, queue]));

  let result = [];
  for (let i = 0; i < data.length; i++) {
    // Use JS behaviour where index keys are iterated in numerical order
    let queuedAt;
    for (queuedAt in sorted) break;
    // Get the queue at this (first) key and remove the entry
    let queue = sorted[queuedAt];
    delete sorted[queuedAt];

    // Extract the element from that queue with the lowest position
    result.push(queue.pop());
    if (queue.length) {
      // Store the shortened queue at its new key
      sorted[MAX - queue[queue.length - 1].enqueuedAt] = queue;
    }
  }
  return result;
}

// Example data from the question:
const data = [{id: 1,enqueuedAt: 8,queueName: 'Queue 1',position: 1},{id: 2,enqueuedAt: 7,queueName: 'Queue 2',position: 1},{id: 3,enqueuedAt: 6,queueName: 'Queue 3',position: 3},{id: 4,enqueuedAt: 5,queueName: 'Queue 4',position: 2},{id: 5,enqueuedAt: 1,queueName: 'Queue 1',position: 2},{id: 6,enqueuedAt: 2,queueName: 'Queue 4',position: 1},{id: 7,enqueuedAt: 4,queueName: 'Queue 1',position: 3},{id: 8,enqueuedAt: 3,queueName: 'Queue 2',position: 2}]

console.log(customSort(data));

最终说明

注意输出的顺序和你的不同，但仍符合你所设定的规则。此解决方案中的顺序 真正地 最大化了enqueuedAt的优先级。

- trincot

Answer 2

一种简短的方法可以

• 按enqueuedAt排序数据，

• 按queueName分组，

• 通过

  • 按position排序任何组，
  • 在临时结果数组中取同一索引处的所有项目，最终

• 获取一个扁平的数组。

const
    data = [{ id: 1, enqueuedAt: 8, queueName: 'Queue 1', position: 1 }, { id: 2, enqueuedAt: 7, queueName: 'Queue 2', position: 1 }, { id: 3, enqueuedAt: 6, queueName: 'Queue 3', position: 3 }, { id: 4, enqueuedAt: 5, queueName: 'Queue 4', position: 2 }, { id: 5, enqueuedAt: 1, queueName: 'Queue 1', position: 2 }, { id: 6, enqueuedAt: 2, queueName: 'Queue 4', position: 1 }, { id: 7, enqueuedAt: 4, queueName: 'Queue 1', position: 3 }, { id: 8, enqueuedAt: 3, queueName: 'Queue 2', position: 2 }],
    result = Object
        .values(data
            .sort((a, b) => b.enqueuedAt - a.enqueuedAt)
            .reduce((r, o) => ((r[o.queueName] ??= []).push(o), r), {})
        )
        .reduce((r, array) => (array
            .sort((a, b) => a.position - b.position)
            .forEach((o, i) => (r[i] ??= []).push(o)),
            r
        ), [])
        .flat();

console.log(result);

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

- Nina Scholz

Answer 3

const data = [
  {
    id: 1,
    enqueuedAt: 8,
    queueName: 'Queue 1',
    position: 1
  },
  {
    id: 2,
    enqueuedAt: 7,
    queueName: 'Queue 2',
    position: 1
  },
  {
    id: 3,
    enqueuedAt: 6,
    queueName: 'Queue 3',
    position: 3
  },
  {
    id: 4,
    enqueuedAt: 5,
    queueName: 'Queue 4',
    position: 2
  },
  {
    id: 5,
    enqueuedAt: 1,
    queueName: 'Queue 1',
    position: 2
  },
  {
    id: 6,
    enqueuedAt: 2,
    queueName: 'Queue 4',
    position: 1
  },
  {
    id: 7,
    enqueuedAt: 4,
    queueName: 'Queue 1',
    position: 3
  },
  {
    id: 8,
    enqueuedAt: 3,
    queueName: 'Queue 2',
    position: 2
  }
]

function sortThem(array) {
  const grouped = {}
  const sorted = []
  
  array.forEach(n => {
    if (!grouped[n.queueName]) {
      grouped[n.queueName] = [n];
      return;
    }
    grouped[n.queueName] = [...grouped[n.queueName], n]
  })
  
  Object.keys(grouped).forEach(n => {
    const sort = grouped[n].sort((a, b) => b.enqueuedAt - a.enqueuedAt)
    sorted.push(...sort);
  })
  
  return sorted
}

console.log(sortThem(data))

类似这样的方法可以解决问题，首先按队列名称对项目进行分组，然后对每个组进行排序并将它们推回数组中。您可能还需要按队列名称进行排序，因为在此示例中它能正常工作是因为队列名称已经按正确顺序排列。

- Ginger Wizard