QuickSort на двойном связанном списке (неправильный вывод)

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; любые изменения, внесенные вами в значения, теряются при возврате swap.

Однако, вы могли бы написать:

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

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

, потому что это обновление полей на два экземпляра узла, которые до сих пор передаются по значению, но это значение является эталонным экземплярам.