Как сделать пузырьковую сортировку с помощью двойного связанного списка? - PullRequest
Новая
       4

Как сделать пузырьковую сортировку с помощью двойного связанного списка?

0 голосов
/ 10 января 2012

У меня есть куча данных в двойном связанном списке, и мне нужно выполнить пузырьковую сортировку числовых данных из этого связанного списка

Это то, что я использовал в прошлом: 

public void bubbleSort(int a[], int n)
{        
  for (int i = 0; i < n-1; i++) 
  {
    for (int j = 0; j < n-1-i; j++)
    {
      if (a[j + 1] < a[j]) 
      {
        int temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }          
    }
  }
}

но я не знаю, как заставить это работать со связанным списком, какая-нибудь помощь?

============================================

Обновление по тому, что я пробовал

Итак, я попробовал этот метод: 

public StudentNode get(int i) {  
    if (!isEmpty()) {  
        int j = 0;  
        StudentNode element1 = header;  
        while (j++ < i) {  
            element1 = element1.getNext();  
            if (element1 == null)  
                return null;  
            }  
            return element1;  
        }  
        return null;  
    }  



public void bubbleSort()
{ 
    for (int i = 0; i < size - 1; i++) { 
        boolean changed = false;  
            for (int j = 0; j < size - i - 1; j++) {  
                if (get(j + 1) != null) {  
                    if (get(j).toBeSortedNumber() > get(j + 1).toBeSortedNumber()) {  
                        System.out.println("Swapping: " + get(j).toBeSortedNumber() + " : " + get(j + 1).toBeSortedNumber());  
                        swap(get(j), get(j + 1));  
                        changed = true;  
                    }  
                }  
            }  
            if (!changed)  
                return;  
        }  
} 

public void swap(StudentNode first, StudentNode second) {
    StudentNode firstPrev = first.goBack();
    StudentNode firstNext = first.getNext();
    StudentNode secondPrev = second.goBack();
    StudentNode secondNext = second.getNext();

        firstPrev.setNext(second);
        firstNext.setBack(second);
        secondPrev.setNext(first);
        secondNext.setBack(first);


    second.setBack(firstPrev);
    second.setNext(firstNext);
    first.setBack(secondPrev);
    first.setNext(secondNext);
}

но он даже не попадает в раздел System.out.println, и я не могу понять, что с ним не так.Больше помочь?

1 Ответ

1 голос
/ 10 января 2012

Поскольку это домашнее задание, я ограничу свой ответ некоторыми подсказками:

  1. Внешний цикл может оставаться как есть.
  2. Внутренний цикл используется для сравнения (и, возможно, обмена) пар последовательных элементов.
    • Вы не можете эффективно использовать произвольный доступ со связанным списком. Однако иметь цикл, который проходит по списку один раз и просматривает каждый элемент и его преемник, очень просто.
    • Замена двух последовательных узлов связанного списка может быть очень простой, если вместо замены самих узлов происходит замена значений , хранящихся в узлах.
...