插入排序對鏈表中的節點進行排序

我試圖使用插入排序方法來排序LinkedList中的節點。我已經調整了很多次這樣的代碼，但我似乎無法得到它，不斷得到不同類型的結果，沒有進行排序。插入排序對鏈表中的節點進行排序

繼承人的代碼：

Node* sort_list(Node* head) 
{ 
    Node* node_ptr = NULL; 
    for(Node* i = head->next; i->next != NULL; i = i->next){ 
      if (i->key < head->key) { 
       node_ptr = i; 
       head = head->next; 
    } 
    } 
    return node_ptr; 
}

來源

2013-10-24 Manny O

在此搜索類似的問題搜索_ [here]（http://stackoverflow.com/questions/16426104/insertion-sort-linked-list-c）_以幫助您理解。 – miqid

Fwiw，這也不會做插入排序（或者其他類型的可描述排序）。根據其定義，插入排序的複雜性正是O（NlogN），這是因爲較低的段使用二進制搜索來定位要插入到已經排序的子序列中的下一個項的位置，任務對於鏈接而言過於簡單列表，但隨機訪問容器是微不足道的。 – WhozCraig

這是一個家庭作業問題，所以不是直接寫代碼，我會先指出你在哪裏錯了。

在插入排序類似的算法中，顯然需要進行某種交換，需要在不合適的元素之間進行交換（即需要插入）。因此，首先考慮如何交換數組中的兩個元素。要特別注意一個人是頭還是一個是尾巴的情況。

您實施的代碼沒有指針交換的任何痕跡，所以這是您錯誤的地方。

接下來，您必須考慮需要排序的情況。在這種情況下，它很簡單。如果當前元素和下一個按排序順序（假設升序，當前<下一個）。然後，不需要做任何事情，只需使下一個最新的。

然後，你可以明顯推斷違反這種情況是當你需要交換元素。交換後（適當注意指針的位置，並在排序後），重複該過程，直到遇到空白牆。

P.S：這是另一個SO問題的可能重複。

來源

2013-10-24 03:14:48

插入排序對鏈表中的節點進行排序

回答

相關問題