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

归并排序对于链表来说更自然，但您可以非常好地进行快速排序。下面是我在几个应用程序中使用的 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;
}