java - 使用带链表的冒泡排序

Question

我正在尝试编写一种方法，该方法将根据每个对象的整数变量（命名优先级）对链表的对象进行排序。我以前用数组列表使用过冒泡排序并且没有遇到任何问题，但是由于某种原因，当我用链表尝试它时，它给了我一个 NullPointerException 并且我不知道我做错了什么。有什么建议吗？

public void sortList() {
    boolean flag = true;
    Item temp = null;
    Item position = head;
    Item positionLink = position.link;
    while(flag) {
        flag = false;
        while (position != null) {
            if(position.getPriority() > positionLink.getPriority()) {
                temp.setItem(position);
                position.setItem(positionLink);
                positionLink.link.setItem(temp);
                flag = true;
                position = position.getItem();
        }
        }
    }
}

Answer 1

你没有初始化temp

 temp.setItem(position);

Answer 2

顺便说一句，你的算法看起来错了.. item.link 和 item.setItem().. 乱七八糟.. 等等..

应该是这样的：

public void sortList() {

    boolean flag = true;
    while (flag) {
        flag = false;

        Item position = head;
        Item positionNext = position.link;
        Item positionPrev = null;

        while (positionNext != null) {
            if(position.getPriority() > positionNext.getPriority()) {

                Item temp = position;
                Item tempNextNext = positionNext.link;
                position = positionNext;
                position.link = temp;
                positionNext = temp;
                positionNext.link = tempNextNext;

                if (positionPrev == null) { // position is head
                    head = position;
                } else {
                    positionPrev.link = position;
                }

                flag = true;
            }
            positionPrev = position;
            position = position.link;
            positionNext = position.link;
        }
    }
}

Answer 3

 public void bubbleSort() {
        boolean swapped;

        do {
        Node curr = first;
        Node prev = null;
        swapped = false;
        while (curr.next != null) {
            Node fwd = curr.next;

            if (curr.item > curr.next.item) {
                /**
                 * 3 pointers involved: prev, temp and temp.next. simply
                 * follow the order
                 * 
                 * prev.next = temp.next; 
                 * temp.next = temp.next.next;
                 * temp.next.next = temp;
                 */

                /**
                 * egde case: prev: can be null temp & temp.next cannot be
                 * null.
                 */

                if (prev != null) {
                    prev.next = fwd;
                } else {
                    first = fwd;
                }
                // advance prev.
                prev = fwd;

                curr.next = fwd.next;
                fwd.next = curr;
                swapped = true;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
    } while (swapped);
}