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

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

使用 comparable 而不是比较器 try with 因为您只比较双精度值。

public class DoubleComp implements Comparable<Double> {

 public int compareTo(Double a1, Double a2) {
  double foo = ((double) a1 - (double) a2);
  return (int) foo;
  }
}

Answer 2

如果您使用 JDK 7 或更高版本，请使用 Double.compare(double d1, double d2) 比较双精度。

排序看起来真的很乱。尝试使用以下方法：

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

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

How do I get insertion sort to work with a doubly linked list

java

sorting

compare

doubly-linked-list

insertion-sort