[音樂播放] 道格·勞埃德：選擇排序是 算法，正如您所料， 排序一組元素。 與算法召回 是一步一步的設置 的用於完成任務的指令。 

在選擇排序 基本思路是這樣， 找到最小的未分類的元素， 其添加到排序的列表的末尾。 有效地這樣做是什麼版本 排序列表，一次一個元件。 將它分解為偽 我們可以說明這個算法 如下所示，重複上述操作直至 沒有排序的元素依然存在。 通過搜索未排序 數據，以找到最小的值， 然後交換的最小值與 未排序的部分的第一要素。 

它可以幫助想像這一點， 讓我們來看看這個。 所以，我主張，是一個 排序的數組，我已經 通過表明所有表示，它 元素為紅色， 它們還未排序。 這是整個 陣列的未分類的一部分。 

因此，讓我們通過以下步驟： 選擇排序該數組進行排序。 所以，再一次，我們要重複 直到沒有未分類的元素依然存在。 我們通過要去搜索 數據，以找到最小的值， 然後交換用該值 未排序的部分的第一要素。 

現在，再次，整個 數組是未排序的一部分。 所有的紅色元素是無序。 所以我們通過搜索和 我們發現的最小值。 我們從頭開始， 我們去年底， 我們發現最小的值，之一。 所以這是第一部分。 然後第二部分，換用該值 未排序部分的第一要素， 還是先紅素。 

在這種情況下，這將是 五，所以我們換一到五。 當我們做到這一點，我們就可以 直觀地看到，我們已經 移動最小的值元素 陣列的，到最開始。 有效地排序的元素。 

因此，我們的確可以確認 並指出之一，排序。 因此，我們將指示排序部分 我們的陣列，通過著色它的藍色。 

現在，我們只需再次重複這個過程。 我們通過對未分類的部分搜索 陣列找到的最小元素。 在這種情況下，它的兩種。 

我們交換與第一 未排序的部分元素。 在這種情況下，雙方還恰好是 未排序部分的第一個元素。 因此，我們交換兩個與自身， 這真的只是留下了兩個 它在哪裡，並且它的排序。 繼續，我們通過搜索 找到的最小元素。 這三種。 我們的第一個交換是 元素，這是五。 現在，三是排序。 

我們通過再次搜索，而我們 找到最小的元素為四。 我們用的第一個元素將其交換 未分類的一部分，現在四是排序。 

我們發現，五是 的最小元素。 我們的第一個交換是 未排序的部分元素。 而現在五是排序。 

然後最後，我們 未分類的部分由 只是一個單一的元件的， 所以我們通過搜索 而且我們發現六是 最小的，而事實上，唯一的元素。 然後，我們可以說，它是排序。 而現在，我們已經關掉我們的數組 被完全未排序 紅色，完全排序 藍色，使用選擇排序。 

那麼什麼是最糟糕的情況嗎？ 那麼在絕對最差 情況下，我們必須過目 所有的數組的元素的 找到最小的未分類的元素， 我們要重複 這個過程n次。 一旦對陣列的每個元素 因為我們只在這個算法中， 在時間排序一個元素。 

什麼是最好的情況？ 那麼它是完全一樣的，對不對？ 實際上，我們必須通過仍然步驟 該陣列的每一個元素 為了確認它， 事實上，最小的元素。 

因此，最壞的情況下運行時，我們 要重複一個過程n次， 一次，每個n個元素。 並且在最好的情況下， 我們必須這樣做。 

所以，回想起我們 計算複雜性的工具箱， 你覺得是最糟糕的 情況下運行時選擇排序？ 你認為什麼是最好的 情況下運行時選擇排序？ 

你猜大O n個平方， 和N大歐米茄平方？ 你是對的。 那些是，事實上，該 最壞的情況下，最好的情況下運行 次，選擇排序。 

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