DOUG LLOYD：所以在CS50，我們了解了 多種排序和搜索的 算法。 有時也可以是 一個小技巧，以保持 跟踪什麼算法做什麼。 我們真的只 撇去表面上也是如此， 還有很多其他的搜索 和排序算法。 所以在這部影片讓我們 只需要幾分鐘的時間 嘗試和提煉每個算法 到其核心要素 這樣你就可以記住的最 有關的重要信息 並能夠闡明 差異，如果有必要的。 

首先是選擇排序。 後面的選擇排序的基本思想 被發現的最小的未分類的元素 在一個陣列，並交換它與 該數組的第一個未排序的元素。 我們說，在最壞情況下 的運行時間為：N的平方。 如果你想召回原因，採取 來看看選擇排序視頻。 最好的情況下運行時間 是也可為N的平方。 

冒泡排序，背後的想法 一個是交換相鄰對。 所以，這可以幫助你的關鍵 記住這裡的區別。 選擇排序是，到目前為止， 找到smallest--泡沫 排序是交換相鄰的一對。 我們交換相鄰的一對 元件的，如果他們 都失靈，從而有效地 泡到右側較大的因素， 並在同一時間它也開始 移動到左側較小的元素。 最壞情況下的情況下運行時間 冒泡排序為n的平方。 最好的情況下運行時間 冒泡排序為n。 因為在這種情況 我們不actually-- 我們可能不需要 做任何掉期的。 我們只需要進行一次 通過在所有n個元素。 

在插入排序中， 這裡基本思路正在發生變化。 這就是關鍵字插入排序。 我們正在經歷步驟一次 從陣列從左到右。 當我們這樣做，我們 要轉變要素 我們已經看到，以騰出空間 較小的需要適應的地方 早在那個排序的部分。 因此，我們所建立的有序陣列中的一個 元件在一個時間，從左到右， 我們的東西轉移，以騰出空間。 最糟糕的情況下的運行時間 插入排序為n的平方。 最好的情況下的運行時間為n。 

合併類別 - 關鍵字 這裡被分割和合併。 我們分裂了全陣列，無論是 這六個要素，八大要素， 萬elements--將其切 降了一半，一半，一半， 直到我們有下陣 正一個元素的數組。 一組N個一個元素的數組。 因此，我們開始與一個 1000元陣， 而我們得到的地步，我們 有1000個一單元陣列。 然後，我們開始合併這些子陣列 回到一起以正確的順序。 因此，我們採取兩個一元的陣列 並創建一個兩元素數組。 我們需要兩兩元素數組 並創建一個四元數組 等等等等，直到我們 再次重修一個n元素的數組。 

最糟糕的情況下的運行時間 歸併排序是N次日誌N。 我們有n個元素，但 這個重新組合的過程 需要記錄n步獲得 回到一個完整的陣列。 運行時，最好的情況下也的n log 5.2，由於這個過程中並沒有真正的 關心陣列是否 排序或不下手。 的過程是相同的，有 沒辦法短路的事情。 因此n日誌N在最壞情況下， N日誌N的最好的情況下。 

我們談了大約兩個 搜索算法。 所以線性搜索是關於迭代。 我們繼續進行跨越陣列 一次，由左到右， 努力尋找數 我們正在尋找。 最壞情況下的運行時間是n的大澳。 這可能需要我們遍歷 橫跨每一個元件 找到我們正在尋找的元素 為，無論是在最後的位置， 或根本沒有。 但是，我們不能確認，直到 我們已經看過了一切。 米最好的情況，我們馬上找到。 最好的情況下的運行時間 線性搜索是1歐米茄。 

最後，出現了二分搜索， 這就需要配套陣列。 請記住，這是一個非常 重要的考慮因素 與二進制搜索工作時。 這是一個先決條件使用它 -  你正在尋找通過數組 必須進行排序。 否則，關鍵字 是分而治之。 拆分數組半 消除一半的元素 每一次當你繼續完成。 由於這種分而治之的 和分裂的事情了一半的方法， 最壞情況下的運行時間 的二進制搜索是 日誌N，其基本上 不是線性搜索n值更好。 在最好的情況運行時間仍為之一。 

我們可能會立即發現 我們第一次做一個劃分，但是， 再次，請記住， 雖然二進制搜索 大大高於線性搜索更好 由於是日誌N對N， 你可能要經過工作 先整理你的陣列中，這 可能會使它不那麼有效視 在迭代排序的大小。 

我是道格·勞埃德，這是CS50。