>> [音樂播放]
道格·勞埃德：選擇排序是 算法，正如您所料，
排序一組元素。
與算法召回 是一步一步的設置
的用於完成任務的指令。
>> 在選擇排序 基本思路是這樣，
找到最小的未分類的元素， 其添加到排序的列表的末尾。
有效地這樣做是什麼版本 排序列表，一次一個元件。
將它分解為偽 我們可以說明這個算法
如下所示，重複上述操作直至 沒有排序的元素依然存在。
通過搜索未排序 數據，以找到最小的值，
然後交換的最小值與 未排序的部分的第一要素。
>> 它可以幫助想像這一點， 讓我們來看看這個。
所以，我主張，是一個 排序的數組，我已經
通過表明所有表示，它 元素為紅色，
它們還未排序。
這是整個 陣列的未分類的一部分。
>> 因此，讓我們通過以下步驟： 選擇排序該數組進行排序。
所以，再一次，我們要重複 直到沒有未分類的元素依然存在。
我們通過要去搜索 數據，以找到最小的值，
然後交換用該值 未排序的部分的第一要素。
>> 現在，再次，整個 數組是未排序的一部分。
所有的紅色元素是無序。
所以我們通過搜索和 我們發現的最小值。
我們從頭開始， 我們去年底，
我們發現最小的值，之一。
所以這是第一部分。
然後第二部分，換用該值 未排序部分的第一要素，
還是先紅素。
>> 在這種情況下，這將是 五，所以我們換一到五。
當我們做到這一點，我們就可以 直觀地看到，我們已經
移動最小的值元素 陣列的，到最開始。
有效地排序的元素。
>> 因此，我們的確可以確認 並指出之一，排序。
因此，我們將指示排序部分 我們的陣列，通過著色它的藍色。
>> 現在，我們只需再次重複這個過程。
我們通過對未分類的部分搜索 陣列找到的最小元素。
在這種情況下，它的兩種。
>> 我們交換與第一 未排序的部分元素。
在這種情況下，雙方還恰好是 未排序部分的第一個元素。
因此，我們交換兩個與自身， 這真的只是留下了兩個
它在哪裡，並且它的排序。
繼續，我們通過搜索 找到的最小元素。
這三種。
我們的第一個交換是 元素，這是五。
現在，三是排序。
>> 我們通過再次搜索，而我們 找到最小的元素為四。
我們用的第一個元素將其交換 未分類的一部分，現在四是排序。
>> 我們發現，五是 的最小元素。
我們的第一個交換是 未排序的部分元素。
而現在五是排序。
>> 然後最後，我們 未分類的部分由
只是一個單一的元件的， 所以我們通過搜索
而且我們發現六是 最小的，而事實上，唯一的元素。
然後，我們可以說，它是排序。
而現在，我們已經關掉我們的數組 被完全未排序
紅色，完全排序 藍色，使用選擇排序。
>> 那麼什麼是最糟糕的情況嗎？
那麼在絕對最差 情況下，我們必須過目
所有的數組的元素的 找到最小的未分類的元素，
我們要重複 這個過程n次。
一旦對陣列的每個元素 因為我們只在這個算法中，
在時間排序一個元素。
>> 什麼是最好的情況？
那麼它是完全一樣的，對不對？
實際上，我們必須通過仍然步驟 該陣列的每一個元素
為了確認它， 事實上，最小的元素。
>> 因此，最壞的情況下運行時，我們 要重複一個過程n次，
一次，每個n個元素。
並且在最好的情況下， 我們必須這樣做。
>> 所以，回想起我們 計算複雜性的工具箱，
你覺得是最糟糕的 情況下運行時選擇排序？
你認為什麼是最好的 情況下運行時選擇排序？
>> 你猜大O n個平方， 和N大歐米茄平方？
你是對的。
那些是，事實上，該 最壞的情況下，最好的情況下運行
次，選擇排序。
>> 我是道格·勞埃德。
這是CS50。