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

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

ИЗМЕНИТЬ

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 ²). Могу ли я использовать mergesort в связанном списке, чтобы иметь лучшую временную сложность?

Спасибо!

Ответ 1

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

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

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

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