算法Java插入排序：“相同”变量得到不同的结果

Question

我用Java做了一个插入排序。 例如，如果我有一个整数数组{8,7,6,5,4,3,2,1}

这将给我一个错误的结果：7,6,5,4,3,2,1,8 picture

public static int[] insertionSort(int[] list) {
    int[] insertionList = list.clone();
    for(int i = 1; i < insertionList.length; i++) {
        int temp = insertionList[i];
        int j = i - 1;
        while(j >= 0 && insertionList[j] > insertionList[i]) {
            insertionList[j + 1] = insertionList[j];
            j--;
        }
        insertionList[j + 1] = temp;
    }
    return insertionList;
}

这将给我我想要的结果：1,2,3,4,5,6,7,8 picture

public static int[] insertionSort(int[] list) {
    int[] insertionList = list.clone();
    for(int i = 1; i < insertionList.length; i++) {
        int temp = insertionList[i];
        int j = i - 1;
        while(j >= 0 && insertionList[j] > temp) {
            insertionList[j + 1] = insertionList[j];
            j--;
        }
        insertionList[j + 1] = temp;
    }
    return insertionList;
}

只是想知道insertionList[i]和temp之间有什么不同。我写了两个println语句来测试这些，但它们也显示了相同的数字

谢谢

Answer 1

while(j >= 0 && insertionList[j] > insertionList[i]) {
            insertionList[j + 1] = insertionList[j];
            j ;
        }

错在这里。插入列表[j+1]=插入列表[j]

在第一次执行中，j+1=i，它将更改insertionList[i]的值

这会影响你的状况

insertionList[j] > insertionList[i]

所以应该改为temp变量