0

嘿，我一直在尝试让插入排序方法适用于我正在学习的类，并且我们被告知使用插入排序对整数链表进行排序，而不使用 Java 库中已经存在的链表类。

这是我的内部节点类，因为我还没有完全掌握循环双向链表的概念，所以我只将其设为单链接

public class IntNode
{
  public int value;
  public IntNode next;
}

这是我在 IntList 类中的插入排序方法

public IntList Insertion()
{
IntNode current = head;

while(current != null)
    {
    for(IntNode next = current; next.next != null; next = next.next)
        {
        if(next.value <= next.next.value)
            {
            int temp = next.value;
            next.value = next.next.value;
                next.next.value = temp;
            }           
        }
    current = current.next;
    }
return this;
}

我遇到的问题是它根本没有排序它通过循环很好但根本没有操纵列表中的值有人可以向我解释我做错了什么我是初学者。

4

3 回答 3

1

您每次都需要从列表中的第一个节点开始，并且循环应该以列表的尾部 -1 结束，如下所示

 public static IntList Insertion()
{
     IntNode current = head;
     IntNode tail = null;
     while(current != null&& tail != head )
     {
       IntNode next = current;
      for( ; next.next != tail;  next = next.next)
    {
    if(next.value <= next.next.value)
        {
        int temp = next.value;
        next.value = next.next.value;
            next.next.value = temp;
        }
    }
    tail = next;
   current = head;
  }
 return this;

}

于 2013-05-07T04:10:05.003 回答
0

插入操作仅在插入的列表已经排序时才有效 - 否则您只是随机交换元素。首先，从原始列表中删除一个元素并从中构造一个新列表——这个列表只有一个元素，因此它是排序的。现在继续从原始列表中删除剩余的元素，随时将它们插入到新列表中。最后，原始列表将为空，新列表将被排序。

于 2013-05-07T03:33:28.813 回答
0

我也同意 Zim-Zam 的观点。插入排序的循环不变量也指定了这一点：“按排序顺序的子数组”。下面是我为插入排序实现的代码，其中我创建了另一个链表，其中包含按排序顺序的元素：

Node newList=new Node();
        Node p = newList;
        Node temp=newList;
        newList.data=head.data;
        head=head.node;
        while(head!=null)
        {
            if(head.data<newList.data)
            {
                Node newTemp = new Node();
                newTemp.data=head.data;
                newTemp.node=newList;
                newList=newTemp;
                p=newList;
            }   
            else
            {
                while(newList!=null && head.data>newList.data)
                {
                    temp=newList;
                    newList=newList.node;
                }
                Node newTemp = new Node();
                newTemp.data=head.data;
                temp.node=newTemp;
                newTemp.node=newList;
                newList=p;
            }

            head=head.node;
        }
于 2017-02-09T00:19:50.093 回答