插入用鏈接列表排序

Question

我正嘗試使用鏈接列表創建插入排序。這是我有：

def insertion_sort(a): 
     """ 
     ------------------------------------------------------- 
     Sorts a list using the Insertion Sort algorithm. 
     Use: insertion_sort(a) 
     ------------------------------------------------------- 
     Preconditions: 
      a - linked list of comparable elements (?) 
     Postconditions: 
      Contents of a are sorted. 
     ------------------------------------------------------- 
     """   
     unsorted = a._front 
     a._front = None 

     while unsorted is not None and unsorted._next is not None: 
      current = unsorted 
      unsorted = unsorted._next 

      if current._value < unsorted._value: 
       current._next = unsorted._next 
       unsorted._next = current 
       unsorted = unsorted._next 
      else: 
       find = unsorted 
       while find._next is not None and current._value > find._next._value: 
        find = find._next 

       current._next = find._next 
       current = find._next 
      a._front = unsorted 

     return a 

我相信我有什麼是正確的排序方面。但是，當我嘗試閱讀主模塊中的列表時，我得到一堆None值。

在這種情況下，插入排序爲而不是在排序時創建新列表。相反，它將所有已排序的元素移動到「前」。總之，我有兩個問題：我不確定插入排序是否正確，並且返回列表a存在問題，因爲它包含None值。在此先感謝

Answer 1

不完全確定的類型是的，但如果你認爲簡單：

class Node: 
    def __init__(self, value, node=None): 
     self._value = value 
     self._next = node 
    def __str__(self): 
     return "Node({}, {})".format(self._value, self._next) 

然後你插入排序並不遙遠，它需要妥善處理好頭的情況下：

def insertion_sort(unsorted):  
    head = None 
    while unsorted: 
     current = unsorted 
     unsorted = unsorted._next 
     if not head or current._value < head._value: 
      current._next = head; 
      head = current; 
     else: 
      find = head; 
      while find and current._value > find._next._value: 
       find = find._next 
      current._next = find._next 
      find._next = current 
    return head 

>>> print(insertion_sort(Node(4, Node(1, Node(3, Node(2)))))) 
Node(1, Node(2, Node(3, Node(4, None))))