>> [音樂播放]
DOUG LLOYD：好吧，所以 冒泡排序是一種算法
你可以用它來進行排序一組元素。
讓我們來看看它是如何工作的。
>> 這樣的基本思想後面 冒泡排序是這樣的。
我們一般要走高 值元素通常到右側，
和一般較低值元素 到左側，如我們所期望的。
我們要下的東西是在 開始時，具有較高的事
是在末端。
>> 我們是如何做到這一點？
那麼在偽代碼， 我們可以說，我們的
設置一個交換計數器為非零值。
我們將看到，為什麼我們這樣做，在第二。
隨後，我們重複以下 過程，直到交換計數為0，
或者直到我們不掉的。
>> 重置互換計數器 0，如果它不是已經0。
然後看每 相鄰的一對元件。
如果這兩個因素是 不是為了，交換它們，
加1到交換櫃檯。
如果你正在考慮 這個你想像它之前，
注意到，這將移動下 值元素向左
和更高的值元素到右側， 有效地做我們想做的事情，
這是將這些團體 在該方式的元件。
讓我們直觀地了解本 看起來使用我們的數組
我們用來測試 這些算法。
我們有一個排序的數組在這裡再次， 通過所有的元素表示
是紅色。
我把我交換反 為非零值。
我隨意選擇 負1--這不是0。
我們想重複這個過程 直到交換計數器為0。
這就是為什麼我把我交換 計數器到一些非零值，
因為否則 交換計數器將是0。
我們甚至不會開始 算法的過程。
如此反复，步驟are-- 復位交換計數器
為0，再看看每個相鄰 對，如果他們不按順序，
交換它們，並添加1 到交換櫃檯。
因此，讓我們開始這個過程。
所以我們要做的第一件事就是 我們設置交換計數器為0，
然後我們開始尋找 在每個相鄰的一對。
>> 所以，我們首先開始看5和2。
我們看到，他們是出 訂貨所以我們交換它們。
我們增加1到交換櫃檯。
所以，現在我們交換計數器1， 和2和5已經被切換。
現在，我們再次重複這個過程。
>> 我們期待下一個相鄰的一對， 5 1--他們也失靈，
所以我們交換他們並添加 1到交換櫃檯。
然後我們來看看5和3。
他們是失靈的，所以我們交換 他們和我們添加1到交換櫃檯。
然後我們來看看5和6。
他們是為了，所以我們實際上並不 這需要時間來交換任何東西。
然後我們來看看6和4。
他們還壞了，所以我們交換 他們和我們添加1到交換櫃檯。
>> 現在可以看到發生了什麼事。
我們已經搬到6一直到結束。
因此，在選擇排序，如果你 看到視頻，我們所做的是
我們結束了移動 建築最小元素
數組排序基本上是從 從左到右，最小到最大。
在冒泡排序的情況下，如果我們 下面這個特殊的算法，
我們實際上將要建設 從右側的排序的數組
到左，從最大到最小。
我們已經有效地冒泡6， 最大值，一直到結束。
>> 因此，我們現在可以宣布 這是排序，
和未來iterations-- 經過陣列again--
我們不必考慮6了。
我們只需要考慮 未排序的元素
當我們正在尋找相鄰的一對。
因此，我們已完成一個 通過冒泡排序。
所以，現在我們回到正題， 重複，直到交換計數器為0。
那麼交換計數器 是4，所以我們要
保持再重複這個過程。
>> 我們要重新交換計數器 為0，並期待在各相鄰對。
因此，我們開始與2 1--他們 壞了，所以我們交換他們
我們增加1到交換櫃檯。
2和3，他們在秩序。
我們不需要做任何事情。
3和5是在順序。
我們不需要做任何事情在那裡。
>> 5和4，它們是從 秩序，因此我們
需要調換並添加 1到交換櫃檯。
而現在我們已經搬到5， 下一個最大的元素，
到未排序部分的端部。
所以，我們現在可以稱之為 排序部的一部分。
>> 現在你在看 屏幕大概可以告訴，
因為我可以，該陣列 排序現在。
但是，我們不能證明呢。
我們沒有擔保 ，它的排序。
但是，這是交換 計數器將開始發揮作用。
>> 因此，我們已經完成了一通。
交換計數器2。
所以，我們要重複 這一過程中再次，
重複，直到交換計數器為0。
重置互換計數器為0。
因此，我們將重新設置。
>> 現在看每一對相鄰。
這是為了，1和2。
2和3是為了。
3和4是為了。
所以在這一點上，注意到我們已經完成 看著每對相鄰，
但交換櫃檯仍是0。
>> 如果我們沒有切換 的任何元件，則它們
必須按順序，由 憑藉這個過程。
於是各種各樣的效率， 我們的計算機科學家喜歡，
是我們現在可以宣布 整個數組必須
進行排序，因為我們沒有 要交換的任何元素。
這是相當不錯的。
>> 那麼什麼是最壞的情況下 場景與冒泡排序？
在最壞的情況下，陣列是 在完全相反的順序，
所以我們要泡每個 大元素的所有
跨越陣列的方式。
我們有效地也有 泡泡所有的小元素後面
在陣列一路，太。
因此，每個n個元件具有移動 在所有其他的n個元素。
所以這是最壞的情況。
在最好的情況下， 場景雖然，這是
略有不同的選擇排序。
該陣列是已經 排序，當我們進去的。
我們沒有做任何 掉期交易在第一輪。
所以，我們不妨來看看 在較少的元素，對不對？
我們並不需要重複此 過處理的次數。
>> 那麼，是什麼意思呢？
那麼什麼是最壞的情況下 對於冒泡排序，這有什麼
在最好的情況下進行冒泡排序？
你猜呢？
在最壞的情況下，你必須遍歷 在所有的n個元素n次。
因此，最壞的情況下為n的平方。
>> 如果數組是完全 雖然排序，你只
來看看每個 的一次的元素。
並且如果交換計數器仍為0， 你可以說這個數組排序。
因此在最好的情況下，這是 實際上比選擇好
類別 - 這是為n的歐米茄。
>> 我是道格·勞埃德。
這是CS50。