单链表的最优快速排序 [英] Optimal Quicksort for Single Linked List

问题描述

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

I am working on implementing a quicksort function to sort singly linked lists. What algorithm would I have to use to accomplish this ? For a linked list it would take worst case O(N) for each comparison, instead of the usual O(1) for arrays. So what would the worst case complexity be ?

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

To sum up, what modifications do I need to make to the quicksort algorithm to have an optimal sorting algorithm and what would be the worst case complexity of the algorithm ?

谢谢！

我在下面有一个实现:

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

推荐答案

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

Mergesort is more natural to implement for linked lists, but you can do quicksort very nicely. Below is one in C I've used in several applications.

人们普遍认为不能对列表进行快速排序.尽管需要谨慎实施，但事实并非如此.

It's a common myth that you can't do Quicksort efficiently with lists. This just isn't true, although careful implementation is required.

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

To answer your question, the Quicksort algorithm for lists is essentially the same as for arrays. Pick a pivot (the code below uses the head of the list), partition into two lists about the pivot, then recursively sort those lists and append the results with pivot in the middle. What is a bit non-obvious is that the append operation can be done with no extra pass over the list if you add a parameter for a list to be appended as-is at the tail of the sorted result. In the base case, appending this list requires no work.

事实证明，如果比较便宜，归并排序往往会运行得更快一点，因为快速排序会花更多时间摆弄指针.但是，如果比较代价高昂，那么快速排序通常会运行得更快，因为它需要的比较少.

It turns out that if comparisons are cheap, mergesort tends to run a little faster because quicksort spends more time fiddling with pointers. However if comparisons are expensive, then quicksort often runs faster because it needs fewer of them.

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

If NODE *list is the head of the initial list, then you can sort it with

qs(list, NULL, &list);

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

Here is the sort code. Note a chunk of it is an optimization for already-sorted lists. This optimization can be deleted if these cases are infrequent.

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

这篇关于单链表的最优快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！