单链表的最佳快速排序算法

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 ;
}

- RagHaven

---

基本上，不要在使用链表样式的数据结构时使用快速排序。你需要使用归并排序。对于任何随机访问为O(n)的数据结构，快速排序都会表现得很差。 - Yuushi

我特别想为了学习目的实现快速排序算法。 - RagHaven

你可以使用 qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) 算法，尽管有些人认为它不是“真正”的快速排序，因为分区不是原地进行的。 - jfs

不要在节点之间移动数据，而是重新排列节点。在分区时，将现有节点构建成两个单独的列表，然后将它们连接起来。 - n. m.

@Yuushi请查看下面的代码。小心使用快速排序，它不需要一般的随机访问，因此在链表上的性能很好。 - Gene

快速排序不需要随机访问，如果您的枢轴选择不需要随机访问。枢轴选择是棘手的部分。 - Joe Z

Answer 1

Mergesort 对于链表来说更自然，但你也可以很好地使用快速排序。下面是用 C 语言实现的一个快速排序算法，我在几个应用程序中都使用过。

存在一个常见的谬论，即不能高效地使用列表进行快速排序。这只是不真实的，尽管需要仔细的实现。

回答您的问题，适用于列表的 Quicksort 算法与适用于数组的算法基本相同。选择一个枢轴（以下代码使用列表的头），将其分为围绕枢轴的两个列表，然后递归地对这些列表进行排序，并将结果与枢轴连接起来。有点不明显的是，如果添加一个参数作为要附加到已排序结果尾部的列表，附加操作可以在不用额外遍历列表的情况下完成。在基本情况下，附加此列表不需要任何工作。

事实证明，如果比较便宜，那么合并排序 tend to 比快速排序运行得稍快，因为快速排序花费更多时间与指针调整相关。但是，如果比较昂贵，则快速排序通常更快，因为它需要更少的比较。

如果 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;
}

- Gene

---

你可以通过交换围绕着枢轴的整个子列表而不是单个元素来提高一些效率，因为在链表中交换子列表的复杂度为O(1)。但这只有在内存写入成为瓶颈时才真正相关。 - Andy

@Andork 谢谢。好主意。虽然这段代码很漂亮（特别是没有针对排序列表的特殊情况），但我会…… - Gene

Answer 2

这是一个Java实现。它使用头作为枢轴。可以通过避免在附加右子列表之前扫描左子列表来进一步改进，但它可以工作。这也是O(nLogn)。

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;
    }

  }
}

- Amorpheus

Answer 3

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

- malejpavouk

---

为什么是-1？这是你可以做到的最好的方式，因为将快速排序应用于链表结构并不是很有意义... - malejpavouk

假设我们想要直接使用快速排序算法对链表进行排序，而不是先将其转换为其他形式，再进行排序，最后再转换回来。虽然问题可能存在漏洞，但这就是一个假设，而不是事实。 - Bernhard Barker

优雅的解决方案，不会失去任何渐近性能。 - alternative

Answer 4

您可以使用以下算法：

• 选择头节点作为中心节点。
• 左分区以中心节点开始，保持其尾部不变
• 右分区开始为空
• 对于每个节点：将其预置到左或右分区列表中之一的头部，设置其next引用为该分区的当前头部，并使其成为其新头部。
• 由于枢轴元素是左分区的尾节点，因此将其下一个引用设置为null，以真正终止该列表。
• 在左右分区上应用递归，返回其可能修改的头引用。
• 将两个排序的子列表连接在一起。由于左分区的尾节点保证保持在那里并且是中心节点，因此将其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!")

- trincot