双链表上的快速排序(Python)

我一直在试图弄清楚并理解如何在python中对双链表进行快速排序。我对快速排序的工作原理有很好的理解,但我一直无法解决这个问题。我曾尝试在线阅读和实现许多版本,但似乎连一些在线代码片段也不是100%正确。例如,我从一个在线源代码中提取代码,确实对他们输入的数字进行了快速排序。然而,对于一组完全随机的数字来说,情况并非如此。我想要一个程序,可以运行任何一组数字,而不仅仅是一些。这里所说的是我的代码,它有时可以工作,但并非适用于所有的数字集。任何帮助都将不胜感激!

# A python program to sort a linked list using Quicksort

# A class that will function as a linked list
class LL_numbers:
    def __init__(self):
        self.head = None
        self.tail = None
    
    # Function that will insert a new node to the end of the linked list
    def push(self, new_data):
        new_node = Node(new_data)

        # If the head is empty fill the head and tail with the new node
        if(self.head == None):
            self.head = new_node
            self.tail = new_node
            return
        
        # If the head is not empty, find the last element (tail) and add an element to the tail
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    def print_list(self):
        current = self.head
        while(current):
            print(current.data, end=", ")
            current = current.next


    def partition(self,left,right):
        i = left.prev
        pivot = right
        j = left

        while(j != right):

            if j.data <= pivot.data:

                # Increment i
                if i == None:
                    i = left
                else:
                    i = i.next
                    i.data, j.data = j.data, i.data
            j = j.next
        # increment i
        if i == None:
            i = left
        else:
            i = i.next
        i.data, right.data = right.data, i.data
        return i
            

    def quickSort(self,left,right):
        if(right != None and left != right and left != right.next):
            p = self.partition(left,right)
            self.quickSort(left, p.prev)
            self.quickSort(p.next,right)


# A node of the doubly linked list
class Node:
    def __init__(self,d):
        self.data = d
        self.next = None
        self.prev = None
  
def main():

    linked_numbers = LL_numbers()

    # 5, 3, 2, 4, 3, 9, 0, 6, 1, 10,
    # for n in range(10):
    #     rand_val = random.randint(0,10)
    #     linked_numbers.push(rand_val)
    linked_numbers.push(5)
    linked_numbers.push(3)
    linked_numbers.push(2)
    linked_numbers.push(4)
    linked_numbers.push(3)
    linked_numbers.push(9)
    linked_numbers.push(0)
    linked_numbers.push(6)
    linked_numbers.push(1)
    linked_numbers.push(10)
    
    

    

    print("Before Quick Sorting:\n")
    linked_numbers.print_list()

    print("\nAfter Quick Sorting:\n")
    print(linked_numbers.tail.data)
    linked_numbers.quickSort(linked_numbers.head, linked_numbers.tail)
    linked_numbers.print_list()

if __name__ == "__main__":
    main()

输出:

Before Quick Sorting:

5, 3, 2, 4, 3, 9, 0, 6, 1, 10,
After Quick Sorting:

10
5, 1, 0, 2, 3, 3, 4, 6, 9, 10,