我编写了一个冒泡排序算法来对链表进行排序。我是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(n2)。我能在链表上使用归并排序来获得更好的时间复杂度吗?