2

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

[编辑]

  • 我想“就地”做这个

  • 我正在寻找有关如何在此过程中管理头部和尾部的帮助。

  • 请不要提出替代方案，除非我的方法是不可能的

4

4 回答 4

1 
//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;
                }
            }
        }
于 2014-05-16T00:52:33.650 回答
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元素时停下来，并确保你不要在它之后交换（但如果需要，元素本身仍然会被交换）。
于 2011-03-29T17:27:26.553 回答
0

对于非破坏性版本，将以下伪代码转换为 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
于 2011-03-29T15:43:40.583 回答
0

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

于 2011-03-29T15:30:06.117 回答