[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 <b的，B <C，等。
或者，你可以按星期幾星期日是低於週一
這是小於星期二。
>> 冒泡排序絕不是一個非常有效的快速排序算法。
最壞情況下的運行是大O的n²
因為你有n次迭代通過列表
檢查所有n個元素，每個傳遞的N×N = N²。
運行時間是指，作為你排序的元素數量增加，
運行時間的增加，二次。
>> 但是，如果效率是你的程序並不是一個大問題
或者，如果你只是少量的元素進行排序，
您可能會發現冒泡排序有用的，因為
它是一個最簡單的排序算法，以了解
和代碼。
這也是一個偉大的方式來獲得經驗與翻譯理論
算法轉換成實際的功能代碼。
嗯，這是給你的冒泡排序。感謝收看。
CS50.TV