带链表的插入排序

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 值。

在这种情况下，插入排序是而不是排序时创建一个新列表。相反，它将所有排序的元素移动到 'front'。

总而言之，我有两个问题：我不确定插入排序是否正确，返回的列表 a 有问题，因为它包含 None 值。提前致谢

Answer 1

不确定 a 的类型，但如果您假设一个简单的：

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

那么你的插入排序就差不了多少了，它需要妥善处理 head case:

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

带链表的插入排序

Insertion Sort with a Linked List

sorting

python-3.x

insertion-sort