Java'da bağlantılı bir listeyi sıralama

Question

Bağlı bir listeyi sıralamak için bir kabarcık sıralama algoritması yazdım. Java'ya yeni başladım ve veri yapılarını öğrenmeye çalışıyorum. İkinci elementimin neden doğru sıralanmadığı konusunda kafam karıştı. Bir kabarcık tür kötü durum senaryosu O (n) olduğunu biliyorum yanında

class SListNode { 
    Object item; 
    SListNode next; 


    SListNode(Object obj) { 
    item = obj; 
    next = null; 
    } 


    SListNode(Object obj, SListNode next) { 
    item = obj; 
    this.next = next; 
    } 

} 
public class SList { 

    private SListNode head; 
    private SListNode temp; 

    public void sortList() { 
     SListNode node = head,i,j; 
     head = node; 
     i = node; 
     j = node.next; 
     while(i.next != null) { 
      while(j.next != null) { 
       if((Integer)i.item < (Integer)j.item) { 
        temp = i.next; 
        i.next = j.next; 
        j.next = temp; 
       } 
       j = j.next; 
      } 
      i = i.next; 
     } 
    } 
} 

Bu

DÜZENLEME Ben

List after construction: [ 3 6 9 4 12 15 ] After sorting: [ 3 4 9 12 6 15 ] 

alıyorum çıkıştır. Daha iyi bir zaman karmaşıklığına sahip olmak için bağlantılı bir listede mergesort kullanabilir miyim?

Teşekkürler!

Answer 1

Bağlantılı listelerde çalışan birçok sıralama algoritması vardır ve bu durumda mergesort mükemmel çalışır. Bağlı listelerdeki birçok klasik sıralama algoritmasını zaman ve alan karmaşıklıkları ile birlikte inceleyen an earlier answer to a question about sorting linked lists yazdım. Bağlı listelerde ekleme sıralama, seçim sıralama, mergesort ve quicksort kullanabilirsiniz. Biraz şekerleme yaparak, aynı zamanda işe yarayabilirsin. Eski yanıtım bunun nasıl yapılacağına dair ayrıntılara sahip.

Kodunuzla ilgili olarak, iç döngünüzde, next işaretçisinin null haline gelinceye kadar ileride j ilerlediğine dikkat edin. Bu noktada, j'u hiçbir zaman başka bir şey olarak sıfırlamazsınız, böylece dış döngünün her zaman iterasyonunda iç döngü hiçbir zaman çalışmaz. Her yinelemenin başlangıcında muhtemelen j = i.next ayarlamalısınız. Ayrıca, j.next boş olduğunda duracaksınız, aksi halde j boş olduğunda, aksi halde dizinin son öğesini atlarsınız. Eğer henüz yerleştirilmemiş olan en küçük elemanı arayan bağlantılı liste üzerinde çok geçer yapıyoruz çünkü

Ayrıca, burada yazdım sıralama algoritması, selection sort ziyade kabarcık tür. Bunun bir sorun olup olmadığını bilmiyorum, ama bunun farkında olsanız bile emin değildim. Bu, sanırım kabarcık türünün çoğu durumda seçimden daha az verimli olduğu (liste zaten sıralanmaya yakın olmadığı sürece), muhtemelen iyi bir şeydir.

Bu yardımcı olur umarız!