插入排序错误

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]，我得到错误的输出。我错过了一些重要的概念吗？插入排序错误

来源

2014-10-04 user3526905

请你可以格式化代码 – 2014-10-04 08:58:13

另外，数组中的第一项索引为零 – 2014-10-04 08:59:00

@EdHeal仅仅因为循环从1开始并不意味着它使用了错误的索引...尤其是在排序算法中。注意'j = i-1' ...在0开始'i'会出错（和UB）。 – 2014-10-04 09:41:11

您的程序看起来对我来说是正确的，但评论显示您不明白其意图。内部循环将原来位于指数严格在j（最终值）和i之间的元素移动到一个位置，从而破坏旧值a[i]。该值已留在temp中，因此temp而不是a[i]应分配给释放的槽a[j+1]，这是程序的功能。

由于极端情况有时会暴露错误，因此您可能会徘徊在a[i]已经大于其之前的任何事情时发生的情况，或者它比之前的任何事情都小。在前一种情况下，您的内循环立即发生，并且j==i-1和temp被放回到a[j+1]即a[i]，这没有效果但是正确;在后一种情况下，您的内部循环运行完毕，并保留j==-1，并且您正在分配a[0]=temp，在这种情况下也是正确的。

来源

2014-10-04 09:09:27

+1为正确和彻底的答案，指出操作系统的混淆，并与其他人提供的垃圾（包括投票结束）的一些对比。 – 2014-10-04 09:54:04

为了使代码更简洁，因此更好，更容易理解

使用一个临时变量来切换值：

for(j=i-1;j>=0;j--){ 
     if(a[j]>temp){ 
      t = a[j+1]; 
      a[j+1] = a[j]; 
      a[j] = t; 
     } 
     else 
      break; 
    }

这些更改后的行：不需要a[j+1]=temp;//if i replace this by a[i] I am getting wrong output. 。

来源

2014-10-04 09:03:31 Igor

如果第一个循环从0开始，第二个循环将从-1开始...... – 2014-10-04 09:04:11

这是无稽之谈...... OP的代码是正确的。 – 2014-10-04 09:44:06

“经过这些更改” - 完美的插入排序会因不必要的交换而降级。 “使代码更简洁，因此更好，更易于理解” - 多么荒谬;你的改变对此无所作为。而你*没有回答OP的问题* ......这就是为什么'a [j + 1] = temp'有效，但'a [j + 1] = a [i]'没有。 – 2014-10-04 20:03:34

插入排序错误

回答

相关问题