继承Iterable<T>的接口默认Comparator排序方法无法交换元素求解决

嘿，我瞅了你的代码，冒泡排序的思路是对的，但核心bug是你只交换了局部变量n1和n2的值，完全没修改链表中的实际元素——这俩变量只是节点内容的临时副本，交换它们跟链表本身半毛钱关系都没有，自然看不到排序效果啦。

来拆解下错误点 #

看这段关键代码：

if(c.compare(n1,n2) > 0){
    T tmp = n2;
    n2 = n1;
    n1 = tmp;
    scambio = true;
}

你在这里交换的是n1和n2这两个局部变量的内存值，但链表节点里存的东西根本没动，相当于你在草稿纸上换了两个数，原账本一点没变，可不就白忙活了嘛。

修复方案：用ListIterator的set()方法改实际元素 #

ListIterator给咱们提供了set()方法，能直接修改当前迭代器指向的节点内容。调整后的逻辑要这么走：

1. 当发现n1和n2需要交换时，先把迭代器回退到n1所在的节点（因为此时迭代器在n2的位置）
2. 用set()把n1的位置换成n2的值
3. 再移回n2的位置，用set()换成原来的n1的值

修改后的完整代码：

default void sort(Comparator<T> c) {
    ListIterator<T> lit = listIterator();
    boolean scambio = true;
    while (scambio) {
        scambio = false;
        T n1 = null;
        T n2;
        if (lit.hasNext()) {
            n1 = lit.next();
        }
        while (lit.hasNext()) {
            n2 = lit.next();
            if (c.compare(n1, n2) > 0) {
                // 回退两步到n1的位置
                lit.previous();
                lit.previous();
                // 把n1的位置替换成n2的值
                lit.set(n2);
                // 前进到n2的位置
                lit.next();
                // 把n2的位置替换成原来的n1的值
                lit.set(n1);
                // 更新n1为交换后的值，继续下一轮比较
                n1 = n2;
                scambio = true;
            } else {
                n1 = n2;
            }
        }
        // 重置迭代器到链表开头，进行下一轮冒泡
        lit = listIterator();
    }
}

额外提一嘴 #

• 注意previous()的使用：当你用next()拿到n2后，迭代器停在n2节点，所以需要两次previous()才能回到n1的位置，移动的时候别搞错步数哈。
• 冒泡排序效率是O(n²)，如果你的链表以后要存大量数据，建议换成归并排序（链表结构天生适合归并，不需要额外空间），不过先把当前的交换问题解决了再说～

内容的提问来源于stack exchange，提问作者user8220814