[音樂播放] 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。