java - 单链表上的快速排序

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

[编辑]

• 我想“就地”做这个

• 我正在寻求有关如何在此过程中管理 head 和 last 的帮助。

• 除非我的方法不可行，否则请不要提出替代方案

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 元素时停下来，并确保您不会在它之后交换(但如果需要，元素本身仍然会被交换)。