java - 单链表递归快速排序的基本情况

Question

我正在努力研究单链表上的递归快速排序。基本情况是什么，当我到达它时我需要做什么才能让函数“倒带”并打印排序列表？这是一些代码，但我认为这是非常错误的...

public static void qSort(SLLNode first, SLLNode last)
{
    SLLNode pivot = first ;
    SLLNode head = pivot.succ ;
    if (first!=last)
    {   
        while (head!=null)
        {
            if (head.data.compareToIgnoreCase(pivot.data)<0)
            {
                pivot.succ = head.succ ;
                head.succ = first ;
                first = head ;
                qSort(first, pivot) ;
                qSort(head, last) ;
            }
            qSort(first, pivot) ;
            qSort(head, last) ;
            }
        }
}

换句话说我的问题:当我到达基本情况 first==last 时，我需要做什么？ 我怎样才能使递归倒带并产生排序列表？

这是我更新后的代码:

public static void qSort(SLLNode first, SLLNode last)
    {
        if (first==last)
        {
            return ;
        }
        SLLNode pivot = first ;
        SLLNode head = pivot.succ ;

        while (head!=null)
        {
            if (head.data.compareToIgnoreCase(pivot.data)<0)
            {
                pivot.succ = head.succ ;
                head.succ = first ;
                first = head ;
                qSort(first, pivot) ;
                qSort(head, last) ;
            }
            qSort(first, pivot) ;
            qSort(head, last) ;
        }
    }

Answer 1

总则

对于快速排序的一般性回顾，您可能应该回顾 quick-sort algorithm on Wikipedia .简而言之，如果您使用 partition 会更容易帮助函数让你的列表进入一个状态，所有小于你的枢轴点的东西都在它的左边，所有大于枢轴点的东西都在它的右边。然后，您可以在枢轴的两边递归调用快速排序。

EJP也有很好的一点。我还没有在链表上看到快速排序。

不管怎样，让我们​​做吧

在我看来，使用链表进行快速排序的算法类似于

def qsort(head, tail)
    if head == tail
        return
    pivot = tail
    current = head
    while current != pivot
        if current.value < pivot.value
            move/prepend current to head of the list
        else
            move/append current to tail of the list
        current = current.next
    qsort(head, pivot-1)
    qsort(pivot, tail)

这有点棘手，因为您必须跟踪 pivot - 1 ，这对于单向链表来说不是很自然。此外，上述算法并没有真正考虑到相等的元素。但一般的想法是你最终得到的所有东西都小于 pivot在它之前，所有比它更伟大的东西都在它之后，然后你调用qsort再次为双方。

你的代码

让我们用一个简单的例子来运行你的程序。

A->B->C->D
F        L

是我们的开始。

SLLNode pivot = first ;
SLLNode head = pivot.succ ;

给我们

A->B->C->D
F  H     L
P  

假设if (head.data.compareToIgnoreCase(pivot.data)<0)给定列表的当前状态，对于每个元素都为真。

所以我们输入if声明，并做

pivot.succ = head.succ ;

A->C->D  B->C
F     L  H
P

head.succ = first ;

B->A->C->D
H  F     L
   P 

first = head ;

B->A->C->D
H  P     L
F 

这给了我们

A->B->C->D
F  H     L
P

B->A->C->D  
H  P     L
F

如果我有那个权利，那么调用

qSort(head, last);

应该是

qSort(pivot, last);

所以你没有调用 qSort再次遍历整个列表。在递归调用 qSort 之前，您似乎还想继续遍历列表，直到小于枢轴的所有内容都在它的左侧。 .