插入排序代码问题：数组索引0元素不符合测试预期求助

你的代码核心问题出在while循环的比较条件上：你在循环中用data[j]和data[i]比较，但在循环过程中，data[i]的值会被data[j]覆盖（当执行data[j+1] = data[j]时，若j+1 == i，data[i]就变成了data[j]的值），导致比较的基准不再是原来要插入的元素，最终插入位置计算错误。

错误代码行 #

while(j >= 0 && compar.compare(data[j], data[i]) > 0)

修复后的代码 #

将比较对象换成提前保存的待插入元素jetzt：

public static<T> void insertSort(T[] data, Comparator<T> compar, Consumer<T[]> output) {
    for (int i = 0; i < data.length; i++) {

        T jetzt = data[i];
        int j = i - 1;

        // 此处修改为比较data[j]和jetzt
        while(j >= 0 && compar.compare(data[j], jetzt) > 0) {
            data[j+1] = data[j];
            j--;
        }

        data[j+1] = jetzt;

        output.accept(data);
    }
}

修复原理 #

jetzt保存了当前要插入的原始元素值，不会被循环中的赋值操作修改，用它和data[j]比较，才能准确找到它应该插入的位置。比如处理数组[3,8,1,...]时：

1. i=2，jetzt=1，j=1
2. 比较data[1]=8和jetzt=1，满足大于0，执行data[2]=8，j=0
3. 再比较data[0]=3和jetzt=1，满足大于0，执行data[1]=3，j=-1
4. 循环结束，将jetzt=1插入j+1=0的位置，数组变为[1,3,8,...]，符合预期结果。

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