實際差別循環

我已經告訴我的老師，這是對冒泡排序實際差別循環

int a[]={2,3,7,9,8,1,4,5,10,6}; 
    for(int i=0;i<a.length;i++) 
    { 
     for(int j=0;j<a.length-i-1;j++) 
     { 
      if(a[j]>a[j+1]) 
      { 
       int t=a[j]; 
       a[j]=a[j+1]; 
       a[j+1]=t; 
      } 
     } 
    } 
    for(int i=0;i<a.length;i++) 
    { 
     System.out.print(a[i]+"\t"); 
    }

獨一無二的代碼，但我有不同的外部環 - 運行程序

int b[]={2,3,7,9,8,1,4,5,10,6}; 
    for(int i=0;i<b.length-1;i++) 
    { 
     for(int j=0;j<b.length-i-1;j++) 
     { 
      if(b[j]>b[j+1]) 
      { 
       int t=b[j]; 
       b[j]=b[j+1]; 
       b[j+1]=t; 
      } 
     } 
    } 
    for(int i=0;i<b.length;i++) 
    { 
     System.out.print(b[i]+"\t"); 
    }

輸出是 - 1日案例 -

1 2 3 4 5 6 7 8 9 10

第二個病例

1 2 3 4 5 6 7 8 9 10

所以現在我被告知我的代碼是錯誤的，即使我的輸出是正確的。請告訴我，我完全錯了嗎？

來源

2014-01-22 The Viper

它看起來像你幾乎「改善」了泡沫排序[雞尾酒排序]（http://en.wikipedia.org/wiki/Cocktail_sort）。 –

我很確定這些年來我至少見過兩種不同的氣泡排序實現，所以聲稱這是「唯一的」有點可疑......事實上，任何聲稱某個特定的代碼是「唯一的」任何東西都應該有點橫向... – twalberg

請考慮訪問academics.se和程序員.se – Pureferret

兩個版本都會排序正確。然而，第一個版本總是會執行一個額外的（不必要的）通行證，因爲它通過了N次，而如果有人考慮它，一個元素可能改變位置的最大次數是N-1（這將是最小/最大數目在陣列的錯誤末端）。所以第二個版本更有效一些，它將複雜度從大約O（N * N）降低到O（N *（N-1））。這在很大程度上是相同的。

所以，你的老師應該認出你的代碼是正確的。由於教師經常被困在他們的思維模型中，所以當你和他談話時要對他進行外交，並小心地引導他得出上面的結論，N-1外部傳球就足夠了。

來源

2014-01-22 15:51:18 Durandal

您的外部循環不會遍歷所有元素。退房b.length-1 for(int i=0;i<b.length-1;i++)。這意味着，如果你有10個元素，你將迭代到第8個元素。由於您同時使用了<和length-1。如果你想堅持.length-1。您應該將條件更改爲i<=b.length-1。

來源

2014-01-22 15:11:13

其實，@The Viper **不需要更改他的代碼。這是因爲最大的元素在開始時被正確放置，因此不需要全部迭代。 – Astrobleme

感謝您的建議。 –

這是冒泡排序的已知優化的開頭：http://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort

來源

2014-01-22 15:23:26 Rhand

實際差別循環

回答

相關問題