如何在 java 中实现插入和排序方法 Comparable array with double link list

Question

我需要帮助，我试图回答但有问题。

我的问题是：

使用addAtFirstSmaller(T t)方法实现Insertion对Comparable数组a进行排序。

用上面的方法实现起来会很简单

1: 创建一个 DoublyLinkedList list.call 它是一个列表。

2：遍历数组a。对于 a 中的每个元素 t，通过以下方式将 t 添加到列表中： lista.addAtFirstSmaller (t);

3：遍历list，将各自的元素放在a中对应的位置。我有方法 addAtFirstSmaller (t)。它运行良好。我尝试了前两个步骤，但我不明白我是如何实施第 3 步的。

我需要帮助。

enter code here
 public Iterator<T> iterator() {

 return new Iterator<T>() {
    
         ListNode<T> node = head.next;

         @Override
         public boolean hasNext() {
          
                 return node != null;
         }

         @Override
         public T next() {
                 
                 if (!hasNext()) {
                         throw new NoSuchElementException();
                 }
                
                 T elem = node.element;
               
                 node = node.next;
             
                 return elem;
         }
         @Override
         public void remove() {
         }
     };
    }
public void addAtFirstSmaller(T t) {

ListNode<T> curr = getLast();

 or a node with value < t
while(curr != head)
{
    if(curr.element.compareTo(t) < 0) 
        break;
    curr = curr.pre;
}

if(curr == head) 
{
    addFirst(t);
}
else
{
  
    ListNode<T> node = new ListNode<T>(curr, curr.pre, t);
   
   
    curr.pre.next = node;
    curr.pre = node; 
}  
}


  enter code here
 public void insertionSort(Comparable[] a) {
    DoublyLinkedList<T> lista = new DoublyLinkedList<T>();

      T  t;
      int ind =0;
 
for(int i = 0; i< a.length; i++) {
     t =  (T) a[i]; 
    
    lista.addAtFirstSmaller(t);
    }
    
    Iterator<T> ite = lista.iterator();
    while(ite.hasNext()) {
     a[ind] = ite.next();
     ind++;
    }
  } 

  // TestClass
  public static void main(string[] args){
    Comparable[] a = new Comparable[5];
    DoublyLinkedList<Integer> lista = new DoublyLinkedList<Integer>();
    a[0] = Integer.valueOf(13);
    a[1] = Integer.valueOf(2);
    a[2] = Integer.valueOf(1);
    a[3] = Integer.valueOf(5);
    a[4] = Integer.valueOf(8);
    System.out.println("The insertion sort för comprable a array is:");
    lista.insertionSort(a);
    System.out.println(lista);}

希望能帮到你

Answer 1

为了迭代从迭代器中获取的元素并将它们放回数组 a 中，您需要两个变量：从 lista.iterator() 中获取的 Iterator 和一个索引进入数组（int）。将索引初始化为 0。对于从迭代器获得的每个元素，将其放入数组中的当前索引处，然后递增索引。这样元素就会被存入a[0]、a[1]、a[2]等

编辑：让迭代器控制迭代循环。我个人更喜欢 while lopp，有些人更喜欢 for 循环。您会在 Internet 上找到关于这两者的大量示例。使用您的搜索引擎。

编辑：迭代器中的这一行看起来有误：

     ListNode<T> node = head.next;

在我看来，您正在初始化 node 以引用列表的 second 节点，从而跳过第一个节点。

编辑：您有两个名为 lista 的变量。您的 main 方法中有一个。 DoublyLinkedList的insertionSort方法中还有一个。在进行插入排序时，您正在将数字填充到后者中。在排序之后你打印前者。所以不要指望打印您的排序列表。但是，如果我理解正确的话，最终目标是对数组进行排序。所以只需打印它：

    System.out.println(Arrays.toString(a));

这应该会给您最终结果。

如何在 java 中实现插入和排序方法 Comparable array with double link list

How to implement insert and sort method Comparable array with double link list in java

java

sorting

linked-list

comparable

insertion