Python 通过交换 node 对链接列表进行 Select 排序

有几个问题:

• 错误的直接原因是您的交换没有正确发生，并且min_sort中的循环在两次迭代和执行progress后会发现first不再有next.这会导致判断while条件时出现错误.

• swap方法不能很好地处理给定 node 是consecutive个 node 的边界情况.在这种情况下，需要更新的链接不是四个，而是三个.但由于您的代码没有专门处理这种情况，因此列表会被"损坏".

• 您的代码会忽略progress中发生的错误.这当然不是好的做法.由于您如何创建具有第一个 node 为伪 node 的列表，因此第一次调用progress将try 将None与一个integer进行比较，并悄然中止progress的执行.

• 创建第一个 node 以None作为数据的列表并不常见:

  self.front = self.Node(None)
  

  尽管您决定使用这样一个始终存在的虚拟 node 来创建您的列表，但这意味着您的方法必须意识到这个特殊 node ，并且永远不会使用其数据，不是用于比较，不是用于输出，不是用于计数，.等

  更常见的情况是not在您的列表中永久存在这样的虚拟 node .您仍然可以创建临时虚拟 node ，但不要真正将其包括在列表中.另一方面，列表构造函数可以以相反的顺序插入给定的值(seq)，这样您甚至不需要伪 node .

• swap不应该仅仅为了找到前任 node 而初始化整个列表.相反，让您的算法让它has个这些前身 node ，然后用those个引用调用swap.

• 声明x, y = y, x在您的swap代码中没有任何意义.虽然它没有任何坏处，但在你使用过它的地方也没有任何好处.你可以省略它.

• 奇怪的是，有时你会用tuple assign来交换值，有时还会用非pythonic使用temp变量来交换值.

• 在progress中，您try 将新找到的最小 node 交换到列表的已排序部分，但您可以通过首先识别最小 node 来保存一些交换，并且只有在循环将that一个交换到位之后.

• 这不是问题，但当您实现可以打印链接列表的函数时，调试变得容易得多.为此，我建议将您的列表列为iterable(实施__iter__).这可以取代您的get_list()方法，因为现在您可以使用原生list()函数获取列表.还利用链接列表可迭代这一事实来建立__repr__方法.一旦您拥有它，您就可以随时打印链接列表，从而简化调试工作.

以下是一个考虑到上述言论的实现:

class LinkedList:
    class Node:
        def __init__(self, data, nxt=None):
            self.data, self.next = data, nxt

    def __init__(self, seq):
        self.front = None  # don't insert a dummy node
        for value in reversed(seq):
            self.front = self.Node(value, self.front)  # prepend

    # Don't provide the nodes to swap, but their predecessors
    def swap_after(self, prev_x, prev_y):
        if prev_x == prev_y: # Nothing to do
            return
        x = prev_x.next
        y = prev_y.next
        if x == prev_y:  # Boundary case
            prev_x.next, x.next, y.next = y, y.next, x
        elif y == prev_x:  # Mirrored boundary case
            prev_y.next, y.next, x.next = x, x.next, y
        else: # Generic case
            prev_x.next, x.next, prev_y.next, y.next = y, y.next, x, x.next

    # Make the list iterable
    def __iter__(self):
        curr = self.front
        while curr:
            yield curr.data
            curr = curr.next

    # Provide a string representation of the list
    def __repr__(self):
        return "->".join(map(repr, self))

    def progress(self, last_sorted, reverse):
        prev_selected = prev = last_sorted
        while prev.next:
            if (prev.next.data > prev_selected.next.data) == reverse:
                prev_selected = prev
            prev = prev.next
        # Swap is only needed when the final selection was made
        self.swap_after(last_sorted, prev_selected)

    def min_sort(self, reverse):
        if not self.front:
            return
        dummy = self.Node(None, self.front)
        last_sorted = dummy
        while last_sorted.next.next:
            self.progress(last_sorted, reverse)
            last_sorted = last_sorted.next
        self.front = dummy.next

def min_sort(seq, reverse=False):
    ll = LinkedList(seq)
    ll.min_sort(reverse)
    return list(ll)


if __name__ == '__main__':
    seq = (4, 30, 8, 31, 48, 19)
    lst = min_sort(seq)
    print(lst)