单链表上的快速排序

Question

我的快速排序不起作用。我特别不确定要传递给分区算法的内容以及如何管理枢轴，因为在一种情况下它成为头节点，在另一种情况下成为最后一个节点。我的方法基于数​​组的解决方案。这是我的尝试。有什么想法吗？请注意，选择分区算法是为了适应单链表 (SLL) 的单向性质。

public static SLL quickSort(SLL list, SLLNode first, SLLNode last)
{
    if (first != null && last != null)
    {
        SLLNode p = partition(list, first, last) ;
        quickSort(list,first,p) ;
        quickSort(list,p.succ, last) ;
    }
    return list ;
}

public static SLLNode partition(SLL list, SLLNode first, SLLNode last)
{
    //last.succ = null ;
    SLLNode p = first ;
    SLLNode 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

链表上快速排序的正常方法是在分区步骤中创建两个（或更好三个，中间的所有元素都等于主元元素）新列表，对第一个和最后一个递归排序，然后将它们连接在一起。

相反，您的代码会交换节点内的数据......有趣。我用以下（子）列表尝试了它：

        first                            last
        [ 5 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]

看看这里你的算法做了什么：

        [ 5 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]
          p
                 ptr

3<5? (yes) {
pivot=5
        [ 3 ]-->[ 3 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]
          p      ptr
        [ 3 ]-->[ 7 ]-->[ 7 ]-->[ 9 ]-->[ 2 ]
          p      ptr
        [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ]
          p      ptr
        [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ]
                  p
                 ptr
}
        [ 3 ]-->[ 7 ]-->[ 5 ]-->[ 9 ]-->[ 2 ]
                  p
                         ptr

这是第一次迭代后的状态。由于 ptr != null，我们现在进入下一次迭代，但我认为您已经可以在这里看到问题了。在下一次迭代之后，它看起来像这样：

        [ 3 ]-->[ 5 ]-->[ 9 ]-->[ 7 ]-->[ 2 ]
                          p
                                 ptr

在下一次迭代中不会发生交换：

        [ 3 ]-->[ 5 ]-->[ 9 ]-->[ 7 ]-->[ 2 ]
                          p
                                         ptr

现在我们将得到一个 NullPointerException，因为 ptr.next == null （或者如果这是一个更大列表的子列表） ，我们会在限制之外进行交换）。

因此，一些想法：

• 在交换步骤中，您应该确保之后 p 指向现在包含枢轴元素的节点。
• 您应该在到达 last 元素时停止，并确保不在它之后进行交换（但如果需要，元素本身仍然会被交换）。

Answer 2

//logic - from left to right, remove smaller node and append at the beginning,
public void partition(int x)// x is your pivot element.
        {
            Node prev = null;
            Node cur = root;
            while (cur!=null)
            {
                if ( cur.data > x || cur == root)
                {
                    cur = cur.next;
                    prev = cur;
                }
                else
                {
                    Node next = cur.next;
                    if (prev != null) prev.next = next;
                    cur.next = root;
                    root = cur;
                    cur = next;
                }
            }
        }

Answer 3

您可能想查看“last.succ = null”行。我认为您可能需要找到其他方法来检查是否已到达要分区的列表段的末尾。事实上，我认为你应该得到一个空指针异常，但我可能是错的。

Answer 4

对于非破坏性版本，请将以下伪代码翻译为 Java：

quickSort list
    | list.isEmpty = empty list
    | otherwise = concat (quickSort lower) (new List(pivot, quickSort upper))
    where
         pivot = list.head
         lower = list of elements from list.tail that are < pivot
         upper = list of elements from list.tail that are >= pivot