如何使插入排序与双链表一起工作

Question

我无法使用此方法对双链表从最小到最大进行排序。

我的输入是：MyLinkedList:3.0、4.0、2.0、69.0、76.0、22.0、341.0、15.0

public void insertionSort(Comparator<? super E> compare) {
DLinkedNode<E> tempI = head.next;    
for (int i = 1; i < size  && tempI.next != null; i++) {      
  E temp = tempI.data;
  int j;
  DLinkedNode<E> tempJ = tempI.prev;
  for (j = i-1; j >= 0 && tempJ.prev != null; j--) {        
    if (compare.compare(tempJ.data, temp) <= 0){
      printLinkedList();
      System.out.println("");
      tempJ.next.data = tempJ.data;                  
    }
    tempJ = tempJ.prev;//j--;          
  }//end for
  tempJ.next.data = temp;      
  tempI = tempI.next;//i++;            
}//end for    
}// end insertionSort

内部for循环每次迭代后的输出为：

MyLinkedList: 3.0, 2.0, 2.0, 69.0, 76.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 2.0, 2.0, 2.0, 76.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 69.0, 2.0, 2.0, 76.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 69.0, 2.0, 2.0, 2.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 69.0, 2.0, 2.0, 2.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 76.0, 69.0, 2.0, 2.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 76.0, 69.0, 2.0, 2.0, 2.0, 341.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 2.0, 2.0, 2.0, 341.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 2.0, 2.0, 2.0, 2.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 2.0, 2.0, 2.0, 2.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 2.0, 2.0, 2.0, 2.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 69.0, 2.0, 2.0, 2.0, 15.0
MyLinkedList: 3.0, 341.0, 22.0, 69.0, 2.0, 2.0, 2.0, 15.0

可比较的方法是：

public class DoubleComp implements Comparator<Double> {
  public int compare(Double a1, Double a2) {
  double foo = ((double) a1 - (double) a2);
  return (int) foo;
  }
}

Answer 1

1. 如果您使用JDK7或更高版本，请使用Double.compare(double d1, double d2)来比较双打

2. 排序看起来真的一团糟。尝试使用以下方法：

   Node root; Comparator comp;
   Node current = root;
   while (current.next != null) {
       E data = current.data;
       Node i = current;
       while (i.previous != null && comp.compare(data, i.previous.data) < 0) {
           i.data = i.previous.data;
           i = previous;
       }
       i.data = data;
       current = current.next;
   }
   

Answer 2

使用comparative而不是comparator try with，因为您只比较两个值。

public class DoubleComp implements Comparable<Double> {
 public int compareTo(Double a1, Double a2) {
  double foo = ((double) a1 - (double) a2);
  return (int) foo;
  }
}