對C中的鏈表進行排序

Question

我被要求編寫一個函數，其中包含3個未排序的鏈接列表，並返回一個包含所有三個列表的單一排序鏈表。什麼是你能想到的最好的方式？

我沒有真正限制內存，但是如果使用/不使用內存限制，你會怎麼做？

Answer 1

鏈表沒有有效的排序算法。 進行數組，排序和重新鏈接。

Answer 2

如果3個列表單獨排序，問題會很簡單，但因爲它們不是更棘手。

我會寫一個函數，它將一個已排序的列表和一個未排序的列表作爲參數，遍歷未排序列表中的每個項目，並依次將其添加到排序列表中的正確位置，直到依次將其添加到排序列表中的正確位置未排序的列表。

然後，簡單地創建一個第四個「空白」列表，根據空白的本質是「排序」，然後用每個未排序列表調用您的方法三次。

將列表轉換爲數組可能會使得事情在能夠使用更高級的排序技術方面更高效一些，但轉換爲數組的成本必須考慮並與原始列表的大小相平衡。

Answer 3

一個選項是在所有三個鏈接列表上使用merge sort，然後使用一個最終合併步驟將它們合併到一個整體排序列表中。

與大多數O（n log n）排序算法不同，合併排序可以高效地在鏈接列表上運行。在一個高層次的，直覺的背後歸併排序一個鏈表如下：

1. 作爲基礎的情況下，如果列表中零個或一個元素，它已經被排序。
2. 否則：
   1. 拆分列表分成大致相等大小的兩個列表，可能通過移動奇數元素到一個列表和偶數元素到另一個。
   2. 遞歸使用合併排序對這些列表進行排序。
   3. 應用merge步驟將這些列表組合到一個排序列表中。

合併算法上鍊表是真的很漂亮。僞碼的工作原理大致如下：

1. 初始化包含結果的空鏈表。
2. 只要兩個列表是不是空：
   1. 如果第一個列表的第一個元素是小於第二列表的第一個元素，將其移動到結果列表的後面。
   2. 否則，將第二個列表的第一個元素移到結果列表的後面。
3. 現在只有一個列表是空的，將所有元素從第二個列表移到結果列表的後面。

這可以在O（n）時間內運行，因此合併排序的整體複雜度爲O（n log n）。

將所有三個列表單獨排序後，可以應用合併算法將三個列表組合爲一個最終的排序列表。或者，您可以考慮將所有三個鏈接列表連接在一起，然後使用巨大的合併排序傳遞同時對所有列表進行排序。沒有明確的「正確方法」來做到這一點;這真的取決於你。

上述算法在Θ（n log n）時間內運行。它也只使用Θ（log n）內存，因爲它沒有分配新的鏈接列表單元，並且只需要在每個堆棧幀中存儲空間來存儲指向各個列表的指針。由於遞歸深度爲Θ（log n），所以內存使用量也爲Θ（log n）。

---

另一個爲O（n log n）的排序，你可以在鏈表實現是quicksort修改。儘管快速排序的鏈接列表版本很快（仍然是O（n log n）），但它並不像在陣列上工作的就地版本那麼快，因爲數組元素的局部性效應不會連續存儲。但是，這是一個應用於列表的非常漂亮的算法。

快速排序背後的直覺如下：

1. 如果你有一個零或一個元素的列表，列表排序。
2. 否則：
   1. 選擇列表中的某個元素作爲數據透視表。
   2. 將列表拆分爲三組 - 元素少於主元，元素等於主元，元素大於主元。
   3. 遞歸排序越來越小的元素。
   4. 將三個列表連接爲較小，然後相等，然後較大以獲取整個排序列表。

之一的快速排序的鏈表版本的漂亮的方面是，所述分隔步驟是比在陣列情況下基本上更容易。選擇數據透視表後（稍後詳細介紹），可以通過爲小於，等於和大於列表創建三個空列表，然後對原始鏈接進行線性掃描來完成分區步驟名單。然後，您可以將每個鏈接列表節點追加/前置到與原始存儲桶對應的鏈接列表中。

獲得這項工作的一個挑戰是挑選一個良好的支點元素。衆所周知，如果樞軸的選擇不好，快速排序可能會退化爲O，但也知道如果隨機選擇一個樞軸元素，則運行時的概率爲O（n log n） 。在一個數組中，這很容易（只需選擇一個隨機數組索引），但是在鏈表中更復雜。最簡單的方法是從0到列表長度之間選擇一個隨機數，然後在O（n）時間內選擇該列表的元素。或者，有一些非常酷的方法可以從鏈表中隨機選取一個元素;這裏描述了one such algorithm。

---

如果你想要一個簡單的算法，只需要O（1）空間，你也可以考慮使用insertion sort到鏈接列表進行排序。雖然插入排序更容易實現，但它在最壞情況下（儘管它也具有O（n）最佳情況行爲）在O（n ）時間內運行，所以它可能不是一個好選擇，除非你特別想要避免合併排序。

插入排序算法背後的想法是如下：

1. 初始化一個空鏈表持有的結果。
2. 對於每3名連接的列表：
   1. 雖然這個鏈表不是空的：在整個結果列表
      1. 掃描，找到位置，其中這個鏈表的第一個元素所屬。
      2. 在該位置插入元素。

---

另一個爲O（n 2 ）排序算法可以適於鏈表是selection sort。這可以通過使用該算法非常容易地實現（假設您有一個雙向鏈表）：

1. 初始化一個包含結果的空列表。
2. 雖然輸入列表不爲空：
   1. 掃描鏈表尋找最小的剩餘元素。
   2. 從鏈接列表中刪除該元素。
   3. 將該元素追加到結果列表中。

這爲O也運行（N ）時間和僅使用O（1）的空間，但在實踐中它比插入排序慢;尤其是它總是運行在Θ（n ）時間。

---

根據鏈接列表的結構，你可能會得到一些非常棒的黑客。特別是，如果您給予加倍鏈接列表，則每個鏈接列表單元格中有兩個指針空間。鑑於此，您可以重新解釋這些指針的含義，做一些相當荒謬的排序技巧。

作爲一個簡單的例子，我們來看看如何使用鏈表列單元來實現tree sort。這個想法如下。當鏈接列表單元格存儲在鏈接列表中時，下一個和上一個指針具有其原始含義。然而，我們的目標是迭代地從連接列表中拉出鏈表，然後將它們重新解釋爲二叉搜索樹中的節點a，其中下一個指針表示「右子樹」，而前一個指針表示「左子樹」。如果你允許這樣做，這裏是實現樹排序一個很酷的方式：

1. 創建一個新的指針鏈表單元，其將作爲指針樹的根。
2. 對於雙向鏈表的每個元素：
   1. 從鏈接的列表中刪除該單元格。
   2. 將該單元作爲BST節點處理，將該節點插入二叉搜索樹中。
3. 做一個按順序步行的BST。每當你訪問一個節點時，從BST中刪除它並將其插回到雙向鏈表中。

這運行在最佳情況下O（n log n）時間和最壞情況O（n ）。在內存使用方面，前兩個步驟只需要O（1）內存，因爲我們從舊指針回收空間。最後一步可以在O（1）空間中完成，也可以使用一些特別聰明的算法。

您也可以考慮以這種方式實施heap sort，雖然這有點棘手。

---

希望這有助於！

Answer 4

我在想你可以應用快速排序。它與合併排序幾乎相同，唯一不同的是你首先分割然後合併，在這裏你首先「合併」然後你分割。如果你看看有點不同的是，歸併快速排序方向相反

歸併：

分裂 - >遞歸 - >合併

快速排序：

umnerge（合併對面） - >遞歸 - >加入（與split相反）

Answer 5

@templatetypedef在流行文章中描述的mergesort算法在O（n lg n）中不起作用。由於鏈表不是隨機訪問，因此步驟2.1 Split the list into two lists of roughly equal size實際上是指對O（n^2 log n）進行排序的整體算法。試想一下。

這裏是一個鏈接，它使用mergesort通過首先將元素讀入數組來排序鏈表 - http://www.geekviewpoint.com/java/singly_linked_list/sort。