Сортировка связанного списка в Java - PullRequest
Новая
       80

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

13 голосов
/ 24 января 2012

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

EDIT 

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;
        }
    }
}

Это вывод, который я получаю 

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

Кроме того, я знаю, что наихудший вариант пузырьковой сортировки - O (n 2 ). Могу ли я использовать сортировку слиянием в связанном списке, чтобы улучшить временную сложность?

Спасибо!

1 Ответ

7 голосов
/ 24 января 2012

Существует много алгоритмов сортировки, которые работают со связанными списками, и сортировка слиянием отлично работает в этом случае.Я написал более ранний ответ на вопрос о сортировке связанных списков , в котором рассматриваются многие классические алгоритмы сортировки связанных списков, а также их временные и пространственные сложности.В связанных списках можно использовать сортировку вставкой, сортировку выбора, сортировку слиянием и быструю сортировку.Приложив немного усилий, вы также получите работу с heapsort.Мой старый ответ содержит подробности о том, как это сделать.

Что касается вашего кода, обратите внимание, что во внутреннем цикле вы продвигаетесь на j вперед, пока указатель next не станет null.На этом этапе вы никогда не переустанавливаете j на что-либо еще, поэтому на каждой будущей итерации внешнего цикла внутренний цикл никогда не выполняется.Возможно, вам следует установить j = i.next в начале каждой итерации.Более того, вы, вероятно, не хотите останавливать цикл, когда j.next равен нулю, а когда j равен нулю, так как в противном случае вы пропустите последний элемент массива.

Кроме того, сортировкаАлгоритм, который вы здесь написали, это сортировка выбора , а не пузырьковая сортировка, потому что вы делаете много проходов по связанному списку в поисках наименьшего элемента, который вы еще не позиционировали.Я не знаю, является ли это проблемой или нет, но я не был уверен, знали ли вы об этом.Тем не менее, я думаю, что это, вероятно, хорошо, поскольку пузырьковая сортировка в большинстве случаев менее эффективна, чем сортировка выбора (если список уже не близок к сортировке).

Надеюсь, это поможет!

...