algorithm - 单链表的最优快速排序

Question

我正在实现一个快速排序功能来对单链表进行排序。我必须使用什么算法来完成这个？对于链表，每次比较都需要 O(N) 的最坏情况，而不是数组通常的 O(1)。那么最坏情况的复杂性是多少？

总而言之，我需要对快速排序算法进行哪些修改才能获得最佳排序算法，以及算法的最坏情况复杂度是多少？

谢谢！

我在下面有一个实现：

public static SingleLinkedList quickSort(SingleLinkedList list, SLNode first, SLNode last)
{
    if (first != null && last != null)
    {
        SLNode p = partition(list, first, last) ;
        quickSort(list,first,p) ;
        quickSort(list,p.succ, last) ;
    }
    return list ;
}

public static SLLNode partition(SinlgleLinkedList list, SLNode first, SLNode last)
{

    SLNode p = first ;
    SLNode ptr = p.succ ;

    while (ptr!=null)
    {
        if (ptr.data.compareToIgnoreCase(p.data)<0)
        {
            String pivot = p.data ;
            p.data =  ptr.data ;
            ptr.data = p.succ.data ;
            p.succ.data = pivot ;
            p = p.succ ;
        }
        ptr = ptr.succ ;
    }
    return p ;
}

Answer 1

Mergesort 对于链表实现起来更自然，但是您可以很好地进行快速排序。下面是我在几个应用程序中使用的 C 语言中的一个。

一个常见的误解是，您不能对列表有效地进行快速排序。这不是真的，尽管需要仔细实施。

为了回答您的问题，列表的快速排序算法与数组基本相同。选择一个枢轴（下面的代码使用列表的头部），围绕枢轴划分为两个列表，然后递归地对这些列表进行排序并将结果附加到中间的枢轴。有点不明显的是，如果您在排序结果的尾部添加要按原样附加的列表的参数，则可以在不额外传递列表的情况下完成追加操作。在基本情况下，添加此列表不需要任何工作。

事实证明，如果比较便宜，则归并排序往往会运行得更快一些，因为快速排序会花费更多时间来摆弄指针。但是，如果比较成本很高，那么快速排序通常会运行得更快，因为它需要的比较少。

如果NODE *list是初始列表的头部，那么您可以使用

qs(list, NULL, &list);

这是排序代码。请注意，其中一部分是对已排序列表的优化。如果这些情况不常见，则可以删除此优化。

void qs(NODE * hd, NODE * tl, NODE ** rtn)
{
    int nlo, nhi;
    NODE *lo, *hi, *q, *p;

    /* Invariant:  Return head sorted with `tl' appended. */
    while (hd != NULL) {

        nlo = nhi = 0;
        lo = hi = NULL;
        q = hd;
        p = hd->next;

        /* Start optimization for O(n) behavior on sorted and reverse-of-sorted lists */
        while (p != NULL && LEQ(p, hd)) {
            hd->next = hi;
            hi = hd;
            ++nhi;
            hd = p;
            p = p->next;
        }

        /* If entire list was ascending, we're done. */
        if (p == NULL) {
            *rtn = hd;
            hd->next = hi;
            q->next = tl;
            return;
        }
        /* End optimization.  Can be deleted if desired. */

        /* Partition and count sizes. */
        while (p != NULL) {
            q = p->next;
            if (LEQ(p, hd)) {
                p->next = lo;
                lo = p;
                ++nlo;
            } else {
                p->next = hi;
                hi = p;
                ++nhi;
            }
            p = q;
        }

        /* Recur to establish invariant for sublists of hd, 
           choosing shortest list first to limit stack. */
        if (nlo < nhi) {
            qs(lo, hd, rtn);
            rtn = &hd->next;
            hd = hi;        /* Eliminated tail-recursive call. */
        } else {
            qs(hi, tl, &hd->next);
            tl = hd;
            hd = lo;        /* Eliminated tail-recursive call. */
        }
    }
    /* Base case of recurrence. Invariant is easy here. */
    *rtn = tl;
}

Answer 2

您可以使用快速排序而不会丢失 O(n*log(n)) 预期行为。诀窍很简单——将节点放入数组，对节点数组进行排序，以正确的顺序重新链接它们。

Answer 3

Here is a java implementation. It uses the head as the pivot. This can further be improved by avoiding the scanning of the left sublist before appending the right sublist, but it works. This is O(nLogn) too.

public class QuickSortLinkedList {

 public ListNode sortList(ListNode head) {

        //Base Case
        if(head == null || head.next == null)
            return head;
        //Partition Strategy
        //Chose first element as pivot and move all elements smaller than the pivot at the end of LL
        //So the order will be pivot, elements smaller than or equal to pivot, elements larger than pivot
        //Example: 9,13,10,6,9,8,11 => 9,13,10,9,11,6,8  and the method will return a pointer to 11
        ListNode partitionedElement = partition(head);

        //The elements to the right of pivot were all smaller than pivot after partioned
        //Example: LeftPartition  = 6->8->null
        ListNode leftPartition = partitionedElement.next;

        //The elements to the left of pivot were all large , so they go in right partition
        //Example: rightPartition = 9->13->10->9->11->null
        ListNode rightPartition = head;
        partitionedElement.next = null;

        //But there can be edge cases
        //Example: 3,5,3,4,5-null => after partition , list is unchanged and last element 5 is returned
        //in this case leftPartition: 3->null and rightPartition 5,3,4,5-null
        if(leftPartition == null){
            leftPartition = head;
            rightPartition = head.next;
            head.next =null;
        }

        //Now Recursively sort
        rightPartition = sortList(rightPartition);
        leftPartition = sortList(leftPartition);

        //After sorting append rightPartition to leftPartition
        ListNode iterator = leftPartition;
        while(iterator.next!=null)
            iterator = iterator.next;
        iterator.next = rightPartition;

        return leftPartition;
    }

    private ListNode partition(ListNode head){
     //Base case
     if(head.next.next == null){

         if(head.next.val>head.val)
            return head.next;
         else
         return head;
     } 

    else{    
        ListNode i = head.next;
        ListNode pivot = head;
        ListNode lastElementSwapped = (pivot.next.val>=pivot.val)?pivot.next:pivot;

        while(i!=null && i.next !=null){

            if(i.next.val >= pivot.val){
                if(i.next == lastElementSwapped.next){
                    lastElementSwapped = lastElementSwapped.next;
                }
                else{
                    ListNode temp = lastElementSwapped.next;
                    lastElementSwapped.next = i.next;
                    i.next = i.next.next;
                    lastElementSwapped = lastElementSwapped.next;
                    lastElementSwapped.next = temp;
                }
            }

            i = i.next;

        }
        return lastElementSwapped;
    }

  }
}

Answer 4

您可以使用此算法：

• 选择头节点作为枢轴节点。
• 左分区以枢轴节点开始，将保持其尾部
• 右分区开始为空
• 对于每个节点：将其预先添加到左侧或右侧分区列表，将其next引用设置为该分区的当前头，并使其成为新头。
• 由于枢轴元素是左分区的尾节点，因此将其下一个引用设置为空，以便真正终止该列表。
• 对左右分区应用递归，返回其可能修改的头引用。
• 将两个排序的子列表绑定在一起。由于左分区的尾节点保证保留在那里并且是枢轴节点，因此将其next引用设置为第二个已排序分区的头。
• 返回排序列表的头部。

当遇到基数时递归停止，即当列表中的节点少于 2 个时。

这具有 O(nlogn) 的平均时间复杂度。最差的时间复杂度是 O(n²)。例如，当列表已经排序时，它将遭受这种时间复杂度。

这是 Python 中的单链表实现，带有一个quick_sort方法：

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

    def __iter__(self):
        curr = self
        while curr:
            node = curr
            curr = curr.next
            yield node

    def values(self):
        return (node.data for node in self)

    def partition(self):
        nodes = iter(self) # All nodes headed by this node
        next(nodes)  # Skip self
        left = self   # Left partition always has pivot node as its tail
        pivotvalue = self.data
        right = None
        for curr in nodes:  # Remaining nodes
            # Prefix the current node to the relevant partition
            if curr.data < pivotvalue:
                curr.next = left
                left = curr
            else:
                curr.next = right
                right = curr
        self.next = None  # Terminate the left partition
        return left, right 
        
    def quick_sort(self):
        if not self.next:  # Base case: one node only
            return self
        left, right = self.partition()
        # Left partition has at least one node (the pivot node, which remains its tail)
        left = left.quick_sort()
        # Right partition could be empty 
        if right:
            right = right.quick_sort()
        self.next = right  # Chain the two sorted partitions
        return left

    def is_sorted(self):
        values = self.values()
        prev = next(values)
        for data in values:
            if data < prev:
                return False
            prev = data
        return True


class LinkedList:
    def __init__(self, *values):
        self.head = None
        self.prefix(*values)
    
    def prefix(self, *values):
        for data in reversed(values):
            self.head = Node(data, self.head)
            
    def values(self):
        if self.head:
            return self.head.values()

    def quick_sort(self):
        self.head = self.head and self.head.quick_sort()

    def is_sorted(self):
        return self.head is not None and self.head.is_sorted()

下面是一些代码，用 20 个值的随机列表反复测试这个实现：

from random import shuffle

values = list(range(20))
for _ in range(100):
    shuffle(values)
    linkedlist = LinkedList(*values)
    print("Shuffled:", *linkedlist.values())
    linkedlist.quick_sort()
    print("Sorted:", *linkedlist.values())
    if not linkedlist.is_sorted():  # Test for failure
        raise ValueError("not sorted!")