java - 对链接列表进行插入排序，数据来自文本文件。 java

Question

我正在使用链接列表进行插入排序，但遇到了问题。

我的数据文件:

Myjob 66
Junk   17
Fun    25
Vital       99
Important   96
MoreFun    28
Work      69
Assignment  44

这是我的插入排序代码

public Node insertSort(Node node){
   Node sortedNode = null;
   while(node != null){
    Node current = node;
    node = node.next;
    Node x;
    Node previous = null;
    for(x = sortedNode; x != null; x = x.next){
        if(current.getData().getNum() > x.getData().getNum()){
                break;
         }
         previous = x;
    }
    if(previous == null){               
          current.next = sortedNode;
          sortedNode = current;
    }
    else{               
       current.next = previous.next;
       previous.next = current;
    }
  }
   sortedNode=head;
  return sortedNode; }

我当前的输出:

Name = Myjob            Priority=66
Name = Assignment            Priority=44
Name = MoreFun            Priority=28
Name = Fun            Priority=25
Name = Junk            Priority=17
null

他们会跳过大于 66 的任何内容。有谁知道如何解决此问题，以便它可以从 99 向下显示到 17？我尝试稍微重新排列文本文件中的顺序，从最高的开始。那么程序就可以完美地执行从99到17的排序。但按照原来的顺序，我的程序只能执行从 66 到最低的排序。我不知道为什么，以及如何解决它？请帮忙。我对 Java 很陌生。非常感谢。

我的数据类

public class Data {

private String name;
private int num;

public Data(){
}

public Data(String name,int num){
    this.name=name;
    this.num=num;
}

public String getName(){
    return name;
}

public void setName(String name){
    this.name=name;
}

public int getNum(){
    return num;
}

public void setNume(int num){
    this.num=num;
}

public String toString()
{
    return "Name = " + name + "            Priority=" + num ;
}

}

这是我的 LinkedList 类:

public class LinkedList {
Node head;
Node prev;
Node cur;


public LinkedList(){

}

public LinkedList(Node head){
    head = null;
}

//getter to get head
public Node gethead(){
    return head;
}

public void printLinkedList(){
    System.out.println(head);
}

public void initializeLL(){
    Node currentNode = head;
    try
    {
        File file = new File("Asg2Data.txt");
        Scanner sc = new Scanner(file);
        while (sc.hasNext())
        {
            Data d = new Data(sc.next(), sc.nextInt());
            Node n = new Node(d);

            if(currentNode == null){
                currentNode = n;
                head = n;
            }else{
                currentNode.setNext(n);
                currentNode = n;
            }
        }
        sc.close();
    }
    catch (Exception ex)
    {
        ex.printStackTrace();
    }
}

public static void main(String[] args) throws FileNotFoundException{

        LinkedList l1 = new LinkedList();
        l1.initializeLL();
        l1.insertSort(l1.head); 
        l1.printLinkedList();
        System.out.println("************");
}
}

这是我的节点类:

public class Node{
Data dt;
Node next;

public Node(){

}
public Node(Data dt){
    this.dt=dt;
}


public Node getNext(){
    return next;
}

public void setNext(Node next){
    this.next=next;
}


public Data getData(){
    return dt;
}

public void setData(Data dt){
    this.dt=dt;
}


public String toString()
{
    StringBuilder sb = new StringBuilder();
    sb.append(dt).append(System.getProperty("line.separator")); 
    sb.append(next).append(System.getProperty("line.separator")); 

    return sb.toString();

}
}

insertionSort 方法位于 LinkedList 类内部。

Answer 1

这里发生了一些事情。首先，您的代码中有一些错误，例如返回尚未更新的 head 。通过在列表的中间开始迭代，这可以轻松解释您所看到的行为。

更重要的是，对我来说这似乎不是插入排序的实现。插入排序是通过在正确的点插入已经排序的列表来完成的。所以看起来像:

sortedList Sort(unsortedlist):
   sortedList = []
   foreach item in unsortedlist:
     sortedList.InsertAtTheRighPlace(item)
   return sortedList