我不認為你的代碼產生的結果應該優先于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 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?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。
