插入排序錯誤

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

插入排序錯誤

回答

相關問題