插入排序鏈接列表

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鍵。玩它瞭解更多。

祝你好運!!!