插入排序错误

Question

int main(){
    int i,j,temp;
    int a[]={3,2,4,7,1};
    for(i=1;i<5;i++){
        temp=a[i];
        for(j=i-1;j>=0;j--){
            if(a[j]>temp)
                a[j+1]=a[j];
            else
                break;
        }
       a[j+1]=temp;//if I replace this by a[i] I am getting wrong output.
    }
    for(i=0;i<5;i++)
        printf("\n\n%d",a[i]);
    return 0;
}

在内部循环中，我不会更改变量i的值，如果我替换了a[j+1]=a[i]，就会得到错误的输出。我是不是错过了一些重要的概念？

Answer 1

你的程序在我看来是正确的，但评论表明你不理解这个意图。内部循环将过去严格位于索引处的元素在j (最终值)和i之间向上移动，从而破坏了a[i]的旧值。该值是在temp中保留的，因此应该将temp而不是a[i]分配给已释放的up槽a[j+1]，这是程序所做的。

由于极端情况有时会暴露bug，所以当a[i]已经比它之前的任何东西都大的时候，或者当它比它之前的任何东西都小的时候，您可能会感到困惑。在前一种情况下，您的内环立即用j==i-1发出，temp返回到a[j+1]中，即a[i]，这没有任何效果，但是正确的；在后一种情况下，您的内环运行到完成，离开了j==-1，而您正在分配a[0]=temp，在本例中也是正确的。

Answer 2

使代码更简洁，从而更好和更容易理解

1. 使用临时变量切换值： 对于(j=i-1；j>=0；j-){ if(aj>temp){ t= aj+1；aj+1 = aj；aj = t；}
2. 这些更改后，行：a[j+1]=temp;//if i replace this by a[i] I am getting wrong output.是不需要的。