插入排序中使用input[i]与current变量为何输出结果不同？

在这段C语言插入排序代码中，内部循环的if条件里用input[i]替代current变量会得到错误输出，用current则结果正确。例如输入数组1 7 4 0 9 4，用input[i]得到1 4 0 7 4 9，用current得到0 1 4 4 7 9。明明二者看似访问的是同一索引的值，为什么结果不同？

void insertionSort(int *input, int size)
{
    int j;
    for(int i=1; i<size; i++){
        int current = input[i];
        for(j=i-1; j>=0; j--){
            if(current < input[j]){
                input[j+1] = input[j];
            }
            else{
                break;
            }
        }
        input[j+1] = current;
    }
}

问题原因 #

核心原因是内部循环里的input[j+1] = input[j]会修改input[i]的值。

当你第一次进入内部循环时，j的初始值是i-1，此时j+1正好等于i。执行input[j+1] = input[j]这行代码时，会把input[i]的原始值覆盖成input[i-1]的值。后续循环再判断input[i]时，它已经不是最初的待插入元素了，而是被前面元素覆盖后的新值，这直接打乱了插入排序的逻辑，导致最终结果错误。

而使用current变量时，我们在进入内部循环前就把input[i]的初始值保存了下来。后续不管数组元素怎么被移动覆盖，current始终保持最初的待插入元素值，排序逻辑就能按照预期执行，得到正确结果。

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