插入排序错误

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]应分配给释放了槽a[j+1],这是该程序的功能.

由于极端情况有时会暴露bug,你可能会在a[i]已经比之前的任何东西更大的情况下徘徊,或者当它比之前的所有东西都小时.在前一种情况下,你的内部循环立即爆发j==i-1,然后temp被放回去a[j+1],这是a[i]没有效果但是正确的; 在后一种情况下,你的内部循环运行完成离开j==-1并且你正在分配a[0]=temp,这在这种情况下也是正确的.