[Powered by Google Translate] [冒泡排序] [JACKSON施泰因坎普哈佛商學院] [這是CS50。 CS50TV] 冒泡排序的排序算法是一個例子 - 也就是說，一個程序的一組中的元素進行排序 升序或降序排列。 例如，如果你想對數組進行排序的數字 [3，5，2，9]，冒泡排序的正確執行，將返回 排序的數組[2，3，5，9]以升序排列。 現在，我要解釋的偽代碼算法是如何工作的。 比方說，我們在排序列表中的5個整數 - 3，2，9，6，5。 該算法開始通過在看的前兩個元素，第3和2， 和檢查，如果他們是彼此的相對順序。 它們是 - 圖3是大於2。 要在升序，他們應該是周圍的其他方式。 因此，我們交換他們。 現在列表看起來像這樣：[2，3，9，6，5]。 接下來，我們來看看第二個和第三個，3個和9。 他們彼此相對正確的順序。 也就是說，圖3是小於9，所以該算法不交換它們。 接下來，我們來看看在9日和6。他們的訂單。 因此，我們需要更換，因為9大於6。 最後，我們來看看在過去的兩個整數，9和5。 他們離開的命令，所以他們必須交換。 在列表中的第一個完整的通過， 它看起來是這樣的：[2，3，6，5，9]。 不壞。這幾乎排序。 但是，我們需要在列表中，再次得到完全排序。 二是小於3，所以我們不交換。 三是小於6，所以我們不交換。 六是大於5。我們交換。 六是小於9。我們不交換。 第二次通過後，它看起來像這樣：[2，3，5，6，9]。完美的。 現在，讓我們把它寫在偽代碼。 基本上，對於列表中的每個元素，我們需要看 直接將其權利和元素。 如果它們是滿分為了相對於彼此的 - 也就是說，如果在左邊的元素 大於一個在右邊 - 我們應該交換這兩個元素。 我們這樣做的每一個元素的列表，我們已經取得了一個通過。 現在我們需要做的直通足夠的時間，以確保清單 是充分，適當的排序。 但是，有多少次，我們必須通過列表 保證我們所做的嗎？ 好了，最壞的情況是，如果我們有一個完全向後列表。 然後，它需要一個數傳遞的數目等於 n-1個元素。 如果這樣做沒有意義的，直觀的，想一個簡單的例子 - 這樣的名單[1]。 這是要採取一個通到正確排序。 [3，2，1] - 最壞的情況是，3個元素排序向後， 這將需要2次迭代進行排序。 一次迭代後，[2，1，3]。 第二個投資收益率排序後的數組[1，2，3]。 所以，你知道，你從來沒有去通過陣列，在一般情況， 超過n-1次，其中n是在數組中的元素數。 因為，這就是所謂的冒泡排序的最大元素趨向於“泡沫” 到很快的權利。 事實上，該算法具有非常有趣的現象。 經過m次迭代整個數組， 最右邊的m個元素是保證 到他們正確的位置進行排序。 如果你想看到這樣的自己， 我們可以嘗試在一個完全向後列表[9，6，5，3，2]。 後通過整個列表， [聲音寫作] [6，9，5，3，2]，[6，5，9，3，2]，[6，5，3，9，2]，[6，5，3，2，9] 最右邊的元素是在適當的地方。 後的第二個直通，6將具有“鼓泡式'的 右數第二位。 這兩個因素將在正確的地方正確的 - 第6和第9 - 經過前兩道直通。 那麼，如何才能使用優化算法呢？ 好了，一個迭代後，通過陣列 我們實際上並不需要檢查一下最右邊的元素 因為我們知道它的排序。 經過兩次迭代，我們知道是肯定的，最右邊的兩個要素都到位。 所以，在一般情況下，通過充分陣列k次迭代後， 檢查最後的k個元素是多餘的，因為我們不知道 他們已經在正確的位置。 因此，如果你的n個元素的數組排序， 在第一次迭代 - 你要排序的所有元素 - 第一n-0。 在第二次迭代中，你必須在所有的元素，但最後看 - 第一n-1。 另一種優化，以檢查是否已排序的列表 在每次迭代之後。 如果它已經對數組進行排序，我們不需要做任何更多的迭代 通過列表。 如何才能做到這一點呢？ 那麼，如果我們不作任何掉期上一通通過的名單， 很明顯，已經排序的列表，因為我們沒有交換什麼。 因此，我們絕對沒有再次進行排序。 也許你可以初始化一個標誌變量，被稱為“不排序” false，然後將其更改為true，如果你要交換的任何元素 通過數組的一個迭代。 同樣，一個計數器來計數多少掉期 在任何給定的迭代。 一個迭代結束時，如果你不交換任何元素， 你知道已排序的列表，你就大功告成了。 冒泡排序，像其他的排序算法，可以 調整，其中有一個排序方法中的任何元素。 也就是說，給定兩個元素，你有辦法說，如果第一個 大於，等於或小於第二個。 例如，你可以說的字母排序 a