我知道如何使用歸并排序對鏈表進行排序。問題是，為什么我們不直接使用堆來創建一個有序的 LinkedList？
- 遍歷鏈表并不斷向最小堆添加專案。
- 繼續從堆中取出專案并堆化堆并添加到新的結果 LinkedList。
第一步將有 O(n) 來遍歷串列并將O(nlogn)專案添加到堆中。總計O(nlogn) [如果我錯了，請糾正我]。
從堆中取出一個專案是O(1)添加一個專案，因為 LinkedList 中的下一個節點是O(1)。[如果這是錯誤的，請糾正我]。
因此，O(nlogn)如果我的理解正確，則可以進行排序。這與歸并排序相同。在記憶體方面，我們使用了一個額外的堆，所以O(nlogn)我可以假設總記憶體。合并排序也可以采用O(nlogn)但可以改進為O(logn).
堆邏輯與“合并k個排序鏈表”相同。我假設每個鏈表都有 1 個專案。
我對堆版本的復雜性可能完全錯誤。如果有人知道不應使用堆的確切原因，請解釋。這不是堆排序，也不是就地演算法。如果時間復雜度是O(n2logn)，我不確定如何。
uj5u.com熱心網友回復：
據我所知，沒有法律禁止使用堆對鏈表進行排序，但請考慮一下：
使用相同的方法，您可以使用用于陣列的任何排序演算法：復制陣列中串列的值；用你最喜歡的演算法對陣列進行排序，然后從陣列中重新創建一個鏈表。
大多數與鏈表相關的代碼挑戰都希望您不要使用任何其他 O(n) 資料結構，而只使用鏈表。根據挑戰，甚至可能需要僅使用 O(1) 輔助記憶體。
如果需要 O(1) 輔助記憶體，那么將鏈表變成堆組織的鏈表是不切實際的：它不能提供從節點到其堆子節點或堆父節點的有效遍歷。另一方面，可以使用鏈表結構實作其他高效演算法，例如歸并排序和某種快速排序。
uj5u.com熱心網友回復：
我知道如何使用歸并排序對鏈表進行排序。問題是，為什么我們不直接使用堆來創建一個有序的 LinkedList？
- 遍歷鏈表并不斷向最小堆添加專案。
- 繼續從堆中取出專案并堆化堆并添加到新的結果 LinkedList。
幾個原因，其中：
漸近復雜性并不是故事的結局。合并排序對于鏈表實作起來特別干凈和高效，因此它是 O(n log n) 鏈表排序中性能最好的之一。
但是漸近復雜性仍然是故事的一部分。通過使用陣列索引之間的關系來提供樹的隱式表示，可以使用 O(1) 輔助空間完成陣列的堆排序。這支持在 O(n log n) 步驟中進行排序，因為按索引訪問陣列是 O(1)，但對于鏈表而言并非如此。要獲得 O(n log n) 堆型別的鏈表，您必須將堆構建為實際的樹或陣列，這需要 O(n) 開銷。然后將其稱為鏈表排序有點緊張，因為您可以對陣列或許多其他資料結構做完全相同的事情。
此外，合并排序很容易變得穩定，但這對于堆排序來說更難，并且可能需要額外的開銷。
所以如果我的理解是正確的，排序可以在 O(nlogn) 中完成。
當然，任何可以在 O(n) 步中列舉的資料集都可以加載到一個陣列中，并通過任何適用的 O(n log n) 陣列排序演算法以 O(n log n) 步進行排序。在鏈表的特殊情況下，還可以將節點重新轉換為排序串列，而不會增加漸近復雜度。
這與歸并排序相同。
相同的漸近復雜度并不意味著相同的性能。常數因子的巨大差異仍然可以產生重要的差異。另外，即使其他所有條件都相同，與您描述的相比，鏈表歸并排序的代碼要簡單得多，這也是一個巨大的工程優勢。這意味著更快的開發和更少的錯誤。
在記憶體方面，我們使用了一個額外的堆，所以我假設總記憶體可以是 O(nlogn)。歸并排序也可以采用 O(nlogn) 但可以改進為 O(logn)。
對于這兩種情況，我不知道您的 O(n log n) 想法來自哪里。在堆排序的情況下，我計算了一個輔助陣列的 O(n) 開銷。在陣列上，典型的合并排序實作有 O(n) 開銷，但在鏈表上，O(log n) 開銷對于合并排序來說是自然的。
關于此評論：
在一本書中，我看到我們將無法使用快速排序或堆排序對單鏈表進行排序。
那本書是錯誤的，即使我們不允許將鏈表讀入輔助陣列或其他資料結構來執行實際排序。如果您確實不允許這樣的輔助結構，那么我認為您不能在少于 o(n 2 log n) 步的時間內對單鏈表進行堆排序，但您可以做到。而且您不需要快速隨機訪問或雙向遍歷來執行 O(n log n) 快速排序。
uj5u.com熱心網友回復：
將專案推入堆并從中彈出都是對數運算。從堆中移除元素是對數的，因為堆需要調整其元素以保證堆不變。所以，你會這樣做2 * n * log n，雖然這在像合并排序這樣的 Big O 術語中仍然是線性的，但它可能更慢。或者至少假設您可以通過使用線性排序演算法而不是使用堆進行排序來做得更好。
你可以做的，我沒有看到你提到它，是將鏈表中的所有元素及時添加到堆的資料存盤中O(n)，然后堆化它，O(n)如果實作正確，它也會運行。然后你會用更好的常數2n n * log n減少到O(n * log n)。
堆使用的額外空間不是O(n log n). 它是線性的，雖然這取決于堆實作，但假設許多標準堆實作都提供了這一點。
將已k排序的鏈表與堆合并時，您將受益于k比鏈表本身的長度小得多的事實。這導致了一個O((n1 n2 ...) * log k)演算法，其中n1, n2,...涉及串列的長度。如果您不使用堆，那么該演算法將O((n1 n2 ...) * k)及時運行。
歸根結底，如果正確實作和使用堆，您將具有用于對鏈表進行排序的線性時間復雜度和線性空間復雜度。但是無論你做什么，所有其他變數都相等，除非有一些特殊要求和約束，否則標準排序演算法在排序時比堆具有更好的常量。讓我重申一下，這兩種方法在 Big O 方面都是線性的，但是排序演算法可以為這個特定目的提供更好的常數，這在現實世界的應用中意義重大。原因是堆需要保證在 O(1) 時間內隨時訪問最小/最大元素。這對其行為施加了限制，并且在排序時您將無法像標準排序演算法那樣對其進行優化。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/361541.html
上一篇：.Net5控制臺后臺服務例外與EntityFrameworkCore的DI
下一篇：從C#中的屬性獲取影像URL