c++ - 插入排序错误

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[ 的旧值我]。该值已在 temp 中保留，因此应将 temp 而不是 a[i] 分配给释放的槽 a [j+1]，这就是程序的作用。

由于极端情况有时会暴露错误，因此您可能会想知道当 a[i] 已经大于它之前的任何内容，或者它小于它之前的所有内容时会发生什么。在前一种情况下，您的内部循环会立即因 j==i-1 中断，并将 temp 放回 a[j+1] > 是a[i]，没有任何效果，但是是正确的；在后一种情况下，您的内部循环运行完成，留下 j==-1 并且您正在分配 a[0]=temp，这在这种情况下也是正确的。