>> 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。