java - 双向链表上的快速排序(输出不正确)

Question

这个问题我已经做了一段时间了。 我创建了一个名为 quickSort.java 的文件——选择列表的最后一个元素作为枢轴元素。并尝试对数字进行排序，但不知何故我无法生成预期的输出。我尝试了很多可能的选择，但我被卡住了!请帮助获得正确的解决方案。

这是我的文件代码:quickSort.java

public void quickFun(Node node)
{
    Node new_node = node;

    /* To find the last element as pivot*/


   while(new_node.next!=null)
    {
        new_node = new_node.next;
    }

    Node head = node;
    Node tail = new_node;
    quickSort(head, tail);
}

public void quickSort(Node head, Node tail)
{       
    Node q = partition(head,tail);

    if(head!=q && head!=q.prev)
    {
       quickSort(head, q.prev);

    }
    if(tail!=q && tail!=q.next)
    {
       quickSort(q.next, tail);
    }

}

public Node partition(Node low, Node high){
    int p = high.data;

    Node i = low.prev;

    for(Node j = low; j!=high; j=j.next)
    {
        if(j.data <= p)
        {              
            if(i==null)
            {
                i = low;
            }
            else
            {
                i = i.next;
            }
            swap(i.data, j.data);
        } 
    }

    if(i==null)
    {
        i = low;
    }
    else
    {
          i = i.next;
    }
    swap(i.data, high.data);
    return i;
}

public void swap(int a , int b)
{
    int t;

    t = a;
    a = b;
    b = t;
}

这里 quickFun 接收插入的 LinkedList 的头部作为参数。 我基本上停留在 quickSort(Node, Node) 条件。

请帮我解决这个问题。

Answer 1

你不能像这样交换值:

public void swap(int a , int b)
{
    int t;

    t = a;
    a = b;
    b = t;
}

Java 是 pass-by-value , 所以 a 和 b 是要交换的局部变量；当 swap 返回时，您对值所做的任何更改都将丢失。

但是，您可以这样写:

public void swap(Node a , Node b)
{
    int t;

    t = a.data;
    a.data = b.data;
    b.data = t;
}

因为这是更新两个节点实例上的字段，它们仍然按值传递，但值是对实例的引用。