插入排序链接列表

Question

我想写一个插入排序方法，但我无法达成协议。下面是我到目前为止的代码，我似乎无法让算法正常工作。 RecordList类包含链接列表的所有方法。 Specificaly，Sort()工程与用户定义的对象Student，其中学生被ID numbers

public class RecordList { 

    private Link first;  //ref to first item 
    private Link last;  //ref to last item 
    int count = 0;   //count number of elms in list 

    //constructor 
    public RecordList(){ 
     first=null; 
     last=null; 
    } 

    //is empty 
    public boolean isEmpty(){ 
     return first==null; 
    } 

    //insert first 
    public void insertFirst(Student dd){ 
     count++; 

     Link newLink = new Link(dd); // make new link 
     if(isEmpty()){ // if empty list, 
      last = newLink; // newLink <-- last 
     } 
     else{ 
      first.previous = newLink; // newLink <-- old first 
      newLink.next = first; // newLink --> old first 
      first = newLink; // first --> newLink 
     } 
    } 

    //insert last 
    public void insertLast(Student dd){ 
     count++; 

     Link newLink = new Link(dd); // make new link 
     if(isEmpty()){ // if empty list, 
      first = newLink; // first --> newLink 
     } 
     else{ 
      last.next = newLink; // old last --> newLink 
      newLink.previous = last; // old last <-- newLink 
     } 
     last = newLink; // newLink <-- last 
    } 

    //delete first 
    //ASSUMES NOT EMPTY 
    public Link deleteFirst(){ 
     count--; 

     Link temp = first; 
     if(first.next == null){ // if only one item 
      last = null; // null <-- last 
     } 
     else{ 
      first.next.previous = null; // null <-- old next 
      first = first.next; // first --> old next 
     } 
     return temp; 
    } 

    //delete last 
    //ASSUMES NOT EMPTY 
    public Link deleteLast(){ 
     count--; 

     Link temp = last; 
     if(first.next == null){ // if only one item 
      first = null; // first --> null 
     } 
     else{ 
      last.previous.next = null; // old previous --> null 
      last = last.previous; // old previous <-- last 
     } 
     return temp; 
    } 

    public boolean insertAfter(Student key, Student dd){ // (assumes non-empty list) 
     Link current = first; // start at beginning 
     while(current.dData != key){ // until match is found, 
      current = current.next; // move to next link 
      if(current == null){ 
       return false; // didn’t find it 
      } 
     } 
     Link newLink = new Link(dd); // make new link 
     if(current==last){ // if last link, 
      newLink.next = null; // newLink --> null 
      last = newLink; // newLink <-- last 
     } 
     else{ // not last link, 
      newLink.next = current.next; // newLink --> old next 
      // newLink <-- old next 
      current.next.previous = newLink; 
     } 
     newLink.previous = current; // old current <-- newLink 
     current.next = newLink; // old current --> newLink 
     return true; // found it, did insertion 
    } 

    //self algorithm 
    public void Sort(){ 
     Link marker = first; 
     Link current = null; 
     Link temp; 

     //if more than one elm sort 
     if(count > 1){ 
      marker = marker.next; 

      //outer loop 
      //until end of list 
      while(marker != null){ 
       current = marker.previous; 
       temp = marker; 

       //inner loop 
       //until position found 
       while(temp.dData.getID() > current.dData.getID()){ 
        if(current == marker.previous){ 
         marker = marker.next; 
        } 
        else{ 
         marker = marker.next; 

         //remove temp from original position 
         if(temp.next == null){ 
          last = temp.previous; 
          last.next = null; 
         } 
         else{ 
          temp.previous.next = temp.next; 
          temp.next.previous = temp.previous; 
         } 

         //check to see if inserting to first elm or not 
         if(current == null){ 
          //insert temp to first 
          //*****CHECK ALGORITHM*****\\ 
         } 
         else{ 
          //insert temp to current.next 
          temp.next = current.next; 
          temp.previous = current; 
          current.next.previous = temp; 
          current.next = temp; 
         } 
        } 
       } 
       //while/else DOES not work 
       else{ 
        //if while condition not met 
        current = current.previous; 

        if(current == null){ 
         //break to outer 
        } 
        else{ 
         //break to inner 
        } 
       } 
      } 
     } 
    } 

    //display 
    @Override 
    public String toString(){ 
     String s=""; 
     Link current = first; 
     while(current != null){ 
      s += current.dData+"\n"+"\n"; 
      current = current.nextLink(); 
     } 
     return s; 
    } 
} 

Answer 1

对不起排序，但你的代码看起来不必要地复杂化。此外，您的代码包含大量的代码，而不仅仅是您的问题所基于的“排序”。如果“排序”是你关心的问题，试试这个。 否则随时可以downvote这个答案，因为堆栈溢出只是在这里来帮助你清除你的概念，然后调试你自己的代码。

这是为插入排序（使用阵列和JavaScript为在浏览器控制台容易检查）的短和甜代码。在浏览器控制台中检查它。一旦你清楚这个想法，就将它扩展到链接列表。尽量保持简单，你会发现你的bug，你会发现你的bug，

var a = [3,1,5,57,9,12,91,45,65,67,89,21,13,56,76,32,77,89,71]; 
console.log('array before sort...' + a); 

//The Insertion Sort 
for(var i=1; i<a.length; i++) { 
    var j = i-1; 
    var key = a[i]; 
    while(j>=0 && a[j] > key) { 
    a[j+1] = a[j]; 
    j--; 
    } 
    a[j+1] = key; 
} 



console.log('array after sort...' + a); 

只需按F12在浏览器中打开控制台。粘贴此代码并按Enter键。玩它了解更多。

祝你好运!!!