使用链接列表进行插入排序

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

不完全确定is的类型，但是如果您假设一个简单的：

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))))