在 python 中使用快速排序对链表进行排序

Question

我是 python 的新手。我在链接列表中存储了以下书籍列表，我想使用快速排序对它们进行排序，但不幸的是，我遇到了一个问题。

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


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append_value(self, x):
        if not isinstance(x, Node):
            x = Node(x)
        if self.is_empty():
            self.head = x
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = x
            x.prev = current
        self.tail = x

    def length(self):
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

    def is_empty(self):
        return self.head is None

    def __str__(self):
        to_print = ''
        current = self.head
        while current:
            to_print += f'{current.data} <-> '
            current = current.next
        if to_print:
            return f'[{to_print[:-5]}]'
        return '[]'

    def quick_sort(self, arr):
        if self.length() < 2:
            return self
        else:
            pivot = self.tail.data
            smaller, equal, larger = [], [], []
            current = self.head
            while current:
                if current.data < pivot:
                    smaller.append(current.data)
                elif current.data == pivot:
                    equal.append(current.data)
                else:
                    larger.append(current.data)
                current = current.next
        return self.quick_sort(smaller) + equal + self.quick_sort(larger)

这是快速排序方法，但它在 'return self.quick_sort(smaller) + equal + self.quick_sort(larger)' 上给我 RecursionError。如何使用快速排序对链表进行排序？

my_list = DoublyLinkedList()
my_list.append_value('In Search of Lost Time')
my_list.append_value('Ulysses by James Joyce')
my_list.append_value('Within a Budding Grove')
my_list.append_value('The Guermantes Way')
my_list.append_value('In Search of Lost Time')
my_list.append_value('Sodom & Gomorrah')
my_list.append_value('One Hundred Years of Solitude')
my_list.append_value('War and Peace')

print(f'List of Books: {my_list}')

print(f'Quick Sort: {my_list.quick_sort(my_list)}')

Answer 1

确实，错误发生是因为您将标准列表传递给 quick_sort，而它期望参数是双向链表实例。

此外，如果在这个算法中允许使用列表，那将是奇怪的，因为那么人们可能会想为什么首先会有一个双向链表。如果您打算使用列表，那么您不妨将数据存储在列表中并对列表进行排序。这不可能是目的。

关于代码的一些其他评论：

quick_sort是class的一个方法，所以应该没有必要将链表也作为参数传递.相反，传递两个参数来标识该链表中子部分的开始和结束节点。
最后的return语句有问题。如果确实 quick_sort 将要 return 链表，那么 + 不是您可以在这些链表上使用的运算符。此外，快速排序应该是一种就地排序算法，而 + 建议创建一个新列表。因为它就地，你应该能够 return self.

所以，......你真的需要通过遍历链表并对其进行操作来解决这个问题。

这是一种方法。首先定义两个方法，允许在链表任意位置插入和删除节点：

def remove_node(self, node):
    if node.prev:
        node.prev.next = node.next
    else:
        self.head = node.next
    if node.next:
        node.next.prev = node.prev
    else:
        self.tail = node.prev
    node.next = node.prev = None
    return node

def insert_after(self, prev, node):
    if not isinstance(node, Node):
        node = Node(node)
    node.prev = prev
    if prev:
        node.next = prev.next
        prev.next = node
    else:
        node.next = self.head
        self.head = node
    if node.next:
        node.next.prev = node
    else:
        self.tail = node
    return self

后者实际上比您已有的 append_value 方法更灵活。你实际上可以利用这个新的来定义你的：

def append_value(self, x):
    return self.insert_after(self.tail, x)

然后按如下进行快速排序：

以开始和结束节点作为参数。从列表中提取（删除）结束节点并将其视为枢轴。让两个引用沿着这个子列表向彼此移动，从末端开始。当它们的值位于枢轴值好的一侧时，让该参考值靠近一点。一旦你有两个值与枢轴相反的引用，交换这两个节点中的数据。一旦这两个引用相互交叉，您就确定了两个分区。将枢轴节点注入回列表中，就在这两个分区之间。最后，使用递归对两个分区做同样的事情：

def quick_sort(self, start=None, end=None):
    if not start and not end:  # set default arguments:
        start = self.head
        end = self.tail
    if not start or not end or start == end or end.next == start:
        # The sublist is empty or has just one value
        return self
    # Extract the pivot node from the list
    end, pivot = end.prev, self.remove_node(end)
    pivotdata = pivot.data
    # Define two references that will walk towards eachother:
    right = end
    left = start
    while left and left.prev != right:  # While they didn't cross over
        if left.data <= pivotdata:
            left = left.next
        elif right.data >= pivotdata:
            right = right.prev
        else: # Swap values, not the nodes:
            left.data, right.data = right.data, left.data
            left = left.next
            right = right.prev
        
    # Insert the pivot node between the two partitions
    self.insert_after(right, pivot)
    # Sort the non-empty partitions recursively
    if start.prev != pivot:
        self.quick_sort(start, right)
    if end.next != pivot:
        self.quick_sort(left, end)
    return self

在 python 中使用快速排序对链表进行排序

Sort linked list by using Quick sort in python

python

linked-list

quicksort