вставка сортировка связанного списка

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

Извините, но ваш код выглядит излишне сложным. Кроме того, ваш код содержит намного больше кода, чем просто «сортировка», на которой основан ваш вопрос. Если «сортировка» вас беспокоит, попробуйте это. В противном случае не стесняйтесь ответить на этот вопрос, потому что Stack Overflow предназначен только для того, чтобы помочь вам очистить свои концепции, а затем отладить собственный код.

Это короткий и сладкий код для вставки сортировки (используя массив и JavaScript для легко проверить в консоли браузера). Проверьте его в консоли браузера. И как только вы поняли эту идею, добавьте ее для Linked List. Старайтесь держать его просто так, и вы найдете ошибку,

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. Играйте с ним, чтобы понять больше.

Удачи !!!