Python中用双向链表实现快速排序

基于比较的排序算法“快速排序”使用分而治之的策略。它将剩余成员分为 2 个子数组（或子列表），具体取决于它们是否小于或大于用作枢轴的元素，该元素从数组中选择为“枢轴”元素（或者，在我们的实例，双向链表）。接下来对子数组进行递归排序。由于数据的链接布局，使用快速排序对双向链表进行排序时有一些特殊注意事项。我们依靠节点操作而不是像数组那样直接索引来进行遍历和重新排序。

双向链表快速排序的主要步骤如下：

分区：选择链表中的枢轴元素构成分区。然后重新排列节点，以便所有值低于主元的节点都放置在它之前，所有值高于主元的节点都放置在它之后。在此分区过程中，节点的下一个和前一个指针会被修改。
递归：快速排序在枢轴节点位于适当位置之前和之后的子列表上的递归应用。
组合：我们最终组合排序的子列表以创建完全排序的双向链表。

class Node:  
    def __init__(self, data):  
        self.data = data  
        self.next = None  
        self.prev = None  
def partition(start, end):  
    pivot = end  
    pivot_value = pivot.data  
    current = start  
    while current != pivot:  
 if current.data <= pivot_value:  
            current = current.next  
        else:  
            current.data, pivot.data = pivot.data, current.data  
        start = current  
    return start  
def quicksort(start, end):  
    if start is None or start == end or start == end.next:  
        return  
    pivot = partition(start, end)  
    if pivot != start:  
        quicksort(start, pivot.prev)  
    if pivot != end:  
        quicksort(pivot.next, end)  
def print_list(head):  
    current = head  
    while current:  
        print(current.data, end=" <-> ")  
        current = current.next  
    print("None")  
def append_node(head, data):  
    new_node = Node(data)  
    if head is None:  
        return new_node  
    current = head  
    while current.next:  
        current = current.next  
    current.next = new_node  
    new_node.prev = current  
    return head  
if __name__ == "__main__":  
    head = None  
    data_list = [3, 6, 1, 9, 4, 2]    
    for data in data_list:  
        head = append_node(head, data)  
    print("Original List:")  
    print_list(head)  
    quicksort(head, None)  
    print("\nSorted List:")  
    print_list(head)

Output:

Original List:
3 <-> 6 <-> 1 <-> 9 <-> 4 <-> 2 <-> None
Sorted List:
1 <-> 2 <-> 3 <-> 4 <-> 6 <-> 9 <-> None

时间复杂性

最佳情况：当使用的枢轴始终将列表分成大致相等的部分时，Quicksort 的最佳时间复杂度就会出现。在这种情况下，时间复杂度为 O(n log n)。
平均情况：当枢轴选择相当随机时，Quicksort 的时间复杂度通常为 O(n log n)。
最坏情况：在最糟糕的情况下，当枢轴选择不断产生不平衡的分割时，Quicksort 的时间复杂度可能会降低到 O(n2) 。不过，通过采用随机枢轴选择或良好的枢轴选择方法，可以降低这种情况的发生率。

快速排序的优势：

高效：Quicksort 以高效著称，在庞大的数据集中，它的性能经常优于其他排序算法。
就地排序：Quicksort 是一种就地排序算法，因此在临时排序时不需要额外的内存来存储元素。这意味着它主要是修改双链表实现中现有节点的指针，从而将内存开销降至最低。
良好的平均性能Quicksort 具有良好的平均性能和 O(n log n) 的时间复杂度，因此非常适合各种应用。

结论
Python 在双链表上的 Quicksort 实现为在这种可适应的数据结构中排序数据提供了一种有用的方法。Quicksort 的双链表变体因其高效性而备受赞誉，尤其是在处理庞大的数据集时，它在发挥 Quicksort 优点的同时，还解决了链表结构所带来的特殊困难。这种实现方式的就地排序功能是其主要优点。与其他排序算法相比，Quicksort 最大限度地减少了内存开销，因此非常适合内存限制严格的应用。该技术通过修改节点的下一个和上一个指针来重新排列元素，而无需分配更多内存。

尽管 Quicksort 具有出色的平均性能，但我们也必须认识到，在最糟糕的情况下，其时间复杂度可能会下降到 O(n2)。通过仔细考虑枢轴选择，并在可行的情况下使用随机化方法，可以降低这种风险。Quicksort 仍然是一种灵活有效的排序算法，可用于双链表中。对程序员来说，Quicksort 是一种有用的工具，因为它高效、内存友好，而且适用于不同的数据集，但前提是应针对特定的使用情况定制枢轴选择算法，以确保始终如一的出色性能。