对数组中的非后续元素进行排序

我不认为你的代码产生的结果应该优先于queuedAt它应该产生的结果。您的算法首先对以queuedAt错误位置顺序出现的元素进行排序，然后交换出现位置顺序的元素，但这并不总是导致尽可能优先的顺序queuedAt。例如，在您的输出中，元素 withqueuedAt=3出现在元素 with之后queuedAt=2，但它们没有理由不能以相反的顺序出现：当它们属于同一队列时，调整后的排序仍会按其位置顺序列出项目，但会优先考虑更大的queuedAt值。建议的算法为了纠正这个缺点并获得更好的时间复杂度，您可以使用最大堆。该堆中的一个条目将对应于一个队列，其所有元素均按排序position。堆使用的键是队列第一个元素的属性，即具有最小值的元素。queuedAtposition然后，您将从堆中选择顶部条目（队列），从该队列中提取第一个元素，并将其推送到最终结果。如果队列尚未为空，则将其保留在堆上，但调整其key，因此它再次对应于queuedAt现在第一个（least position）的队列元素的属性。如果队列已耗尽，则将其从堆中删除。如果您继续这样做直到堆被清空，您将按照所需的顺序访问条目。不幸的是，JavaScript 没有本机堆实现。所以你必须扔掉你自己的，或者包括一个库（有几个）。在下面的实现中，我选择以相反的顺序对队列进行排序，因此我可以按所需的顺序弹出元素。开始了：/* MinHeap minimised - taken from https://stackoverflow.com/a/66511107/5459839 */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 functionfunction 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 32）：我们可以利用 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。

对数组中的非后续元素进行排序

3回答