氣泡排序算法中的外環

我一直在谷歌上搜索，並且找不到類似的問題或解釋。氣泡排序算法中的外環

假定以下代碼：

int out, in; 
for(out=nElems-1; out>1; out--) 
    for(in=0; in<out; in++) { 
     if(a[in] > a[in+1]) 
      swap(in, in+1); 
    }

當外值達到1後爲什麼外循環停止？它不應該有2個元素嗎？ 0和1的地方？是什麼讓我們確信他們已經被分類？

我明白這個算法是如何工作的，並且意識到如果沒有完成迭代就會停止一個標誌，這會有更好的解決方案，但是我對理解上面的代碼非常感興趣。

來源

2014-09-13 Lifter

不應交換是'交換（一個[IN] ，a [in + 1]）'？你擁有它的方式是交換索引，而不是實際排列數據 – nem035 2014-09-13 18:04:11

你試過對上面的代碼做空運行嗎？ – zerocool 2014-09-13 18:05:35

從書中複製而來。虛擬交換會照顧到這一點。 :) – Lifter 2014-09-13 18:05:43

當輸出達到2時，內循環從0變爲1.它確保[0]和[1]兩個元素的順序正確 - 這是停止冒泡排序的時間。然而，上面提供的代碼會比較[1]和[2] - 導致潛在的交換導致未排序的數組（因爲[1]和[2]之後[0]和[1]應該再次進行比較相比）。爲了使這個代碼正常工作，外層循環應該包含在內，所以for (out = nElems - 1; out > 0; out--)。

你需要在這裏看到的事實是，在氣泡排序內部循環正在做排序的實際工作（通過交換元素）。外層循環只是設置超出所有元素已經排序的限制。

來源

2014-09-13 18:06:35 3yakuya

你錯了，它確保[0]和[1]的順序正確，但是[2]可能會取代[1]和它沒有被檢查[0] – Kyborek 2014-09-13 18:32:35

啊，我明白了。該書的代碼似乎是錯誤的。一個[in + 1]是我沒有看到的東西。謝謝。 – 3yakuya 2014-09-13 19:27:48

所以，恐怕這本書代碼不起作用，讓我們通過實例證明：

Array ={3,2,1};//nvm the syntax, i assume pseudocode because we don't even know what is swap() 
nElems=3; 
For: out=2; 
For:in=0 
    check 0 and 1 
    Array={2,3,1} 
in=1 
    check 1 and 2 
    Array={2,1,3} 
in=2, break; 
out=1, break;

你可以看到流量與數組{2,1,3}這是沒有排序結束。因此，即使書本可能有錯誤，或者如果你閱讀了幾頁，你可能會發現它是故意的。正確冒泡排序將具有條件out>=1或out>0

編輯：用陣列由2種元素的，算法將什麼都不做，甚至simplier證明

Array ={2,1}; 
nElems=2; 
For: out=1, break;//out = nElems-1, 1>1 is false

來源

2014-09-13 18:06:47 Kyborek

這個循環是否會說'out = 1'，這個時候不會中斷，因爲終止條件是out> 1'。我錯了嗎，還是不清楚東西？我可能是錯的，但我猜更多的是困惑。 – 2014-09-13 18:18:50

你說得對，讓我重新思考 – Kyborek 2014-09-13 18:24:30

氣泡排序算法中的外環

回答

相關問題