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

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

一般来说，

对于快速排序的一般回顾，您可能应该回顾一下 快速排序-维基百科上的排序算法。简而言之，如果您使用 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) 为 true。

所以我们输入 if 语句，然后 do

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

如果我有这个权利，那么对 Should 的调用

qSort(head, last);

可能会是

qSort(pivot, last);

所以你不会在整个过程中调用 qSort再次列出。似乎您可能想继续浏览列表，直到小于枢轴的所有内容都位于列表的左侧，然后再递归调用 qSort。

Answer 2

研究链表的快速排序是一件有用的事情。在研究任何算法时，重要的是要了解绝对需要什么。

在这种情况下，人们发现不需要随机访问迭代器。事实上，前向迭代器就足够了。
Stepanov 在 STL 中的大量工作就是提取此类信息。

这是一个简单的 C++ 实现。抱歉更改语言。
我只是交换数据而不是节点指针。后者与快速排序无关。

是的，我知道我对枢轴元素的选择可能会引起问题。
人们可以找到第一个和最后一个之间的距离 d，然后在 [0, d) 范围内选择一个随机数 x。现在将初始化为first的指针前进x次，并将其数据与first指向的数据交换。

struct Node
{
    Node(int d) : data(d), next(0) {}
    ~Node() { delete next; }
    Node* next;
    int data;
};

void Quicksort(Node* first, Node* last)
{
    if (first == last)
    {
        return;
    }

    Node* pivot = first;
    Node* boundary = first;
    for (Node* it = first->next; it != last; it = it->next)
    {
        // Invariant:
        // The iterators in the range [first, boundary->next) 
        // point to nodes with data less than the pivot
        // element's.
        // The iterators in the range [boundary->next, it) 
        // point to nodes with data greater or equal to 
        // the pivot element's.

        if (it->data < pivot->data)
        {
            // Swap the data to maintain the invariant
            boundary = boundary->next;
            std::swap(it->data, boundary->data);
        }
    }

    // Put the pivot data in its right place
    std::swap(pivot->data, boundary->data);

    Quicksort(first, boundary);
    Quicksort(boundary->next, last);
}

最初的调用会是这样的

Quicksort(head, 0);

Answer 3

基本情况是一个包含 0 或 1 个元素的列表。

Answer 4

你不需要“倒带”。当您进行递归调用时，它会在调用完成时返回递归堆栈。

如果（第一个==最后一个）返回；

Answer 5

从概念上讲，请注意，在 first==last 的基本情况下，您有一个元素的链接列表，因此它已经排序。

我认为你的算法可能略有偏差？您需要一个循环，将小于枢轴的所有内容移动到上半部分，将大于枢轴的所有内容移动到下半部分。然后（循环完成后！）您可以递归地对两半进行排序。我发现你的做法有点不同，但我不相信这是正确的......

最后，正如其他人所说，对链接列表进行排序并不是一项非常有用的任务。你不会用自行车来拖拖车......