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