[Powered by Google Translate] TOMMY：讓我們來看看在選擇排序的算法 的號碼列表和排序。 一種算法，記住，是一個簡單的一步一步的 完成任務的過程。 選擇排序的基本理念是將 我們的名單分為兩部分 -  一個的排序部分和未排序的部分。 該算法在每個步驟中，一個數字移動從 直到最後的排序條件部分的未分類的部分 整個列表進行排序。 所以這裡有一個列表中的六個數字 -  23，42，4，16，8，和15。 現在被認為是整個列表排序。 即使16這樣的數字可能已經在其正確的 位置，我們的算法有沒有辦法知道，直到 整個列表進行排序。 因此，我們會考慮每一個數字無序的，直到我們整理 它自己。 我們知道，我們要以升序排列的列表。 因此，我們將要建立我們的名單的排序部分 由左到右，從最小到最大。 要做到這一點，我們需要找到最小的未分類的元素 並把它在排序的部分結束。 由於此列表未排序，只有這樣，才能做到這一點是 看在未排序的部分，記憶中的每個元素 哪一個元素是最低的和比較 每個元素。 因此，我們將首先在23。 這是我們所見過的第一個元素，所以我們會記住 它作為最低。 接下來，我們看42。 42是大於23，所以23仍然是最低。 其次是4，這是小於23，所以我們會記住4 作為新的最小值。 接下來是16，這是大於4，所以4 仍然是最低。 圖8是大於4，和圖15是大於4，所以4必須是 最小的未分類的元素。 因此，即使作為人類，我們可以立即看到，4 最小的元素，我們的算法需要看 每一個未排序的元素，即使我們已經找到了4  -  最小的元素。 所以，現在，我們已經發現的最小元素，4，我們將要 將它移動到列表的排序部。 由於這是第一個步驟中，這意味著我們希望把4日 在列表的開頭。 現在圖23是在列表的開頭，所以 讓我們交換的4個和23個。 所以，現在我們的名單看起來是這樣的。 我們知道，4必須是在其最終位置，因為它是 兩個最小的元素和元素的開頭 的列表。 因此，這意味著，我們永遠不需要再次移動它。 因此，讓我們重複此過程，添加另一個元素 排序的列表中的部分。 我們知道，我們並不需要，因為它是在4 已經排序。 因此，我們就可以開始的42個，我們會記住的 最小的元素。 所以接下來我們來看看23小於42，所以我們 記得23是新的最低。 接下來，我們看到這是小於23的16，所以 16是新的最低。 現在我們來看看在8小於16，所以 圖8是新的最小值。 和最後8是小於15，因此，我們知道，圖8是一個最小 未分類的元素。 因此，這意味著我們應該附加的排序 列表中的部分。 現在是唯一的排序元素，所以我們想要把 接下來的8到4。 由於42是第一要素，在未排序的部分 名單中，我們將要交換42和8。 所以，現在我們的名單看起來是這樣的。 圖4和圖8表示排序的列表中的部分，並 剩下的數字表示未分類的 列表中的部分。 因此，讓我們繼續進行下一次迭代。 我們從23日的時間，因為我們不需要看 在4和8了，因為他們已經 已排序。 16小於23，所以我們會記住 16作為新的最小值。 圖16是小於42，但圖15是小於16，所以15必須是 最低未分類的元素。 所以，現在我們要交換15日和23日至 在此給我們的清單。 已排序的列表中的部分由4，8和15，以及 這些元素依然排序。 但它只是恰巧下一個未排序的元素，16， 已經排序。 然而，有沒有辦法知道我們的算法，16 已經在正確的位置，所以我們仍然需要 重複完全相同的相同的過程。 所以我們看到，圖16是小於42，和圖16是小於23，所以 16必須的最小元素。 交換這個元素本身，這是不可能的，所以我們可以 簡單地離開這個位置。 因此，我們需要一個更通過我們的算法。 圖42是大於23，所以23必須是 最低未分類的元素。 一旦我們交換23和42，我們結束了我們的最終 排序的列表 -  4，8，15，16，23，42。 我們知道42必須在正確的地方，因為它是 唯一的元素離開，這就是選擇排序。 現在讓我們來規範我們的算法與一些 偽代碼。 線一條，我們可以看到，我們需要將超過 列表中的每一個元素。 除了最後一個元素中，由於第1族元素 已排序的列表。 線兩條，我們認為未排序的第一個元素 部分的列表中是最低的，因為我們沒有與我們的 例如，我們有一些比較。 第三行開始第二個循環中，我們遍歷 每一個未排序的元素。 我們知道後，我迭代，排序的部分 我們的名單必須有i個元素，因為每一步 一種元素進行排序。 因此，第一個未排序的元素必須是在位置i加1。 第四行中，我們比較了當前元素的最低 元素，我們已經看到了這麼遠。 如果當前元素是小於最小 元素，那麼我們記住當前的新元素 最低線5。 最後，在六，七行，我們交換最低 元件與所述第一未排序的元件，從而 將其添加到列表的排序部。 一旦我們有一個算法，一個重要的問題要問 自己作為程序員了多長時間？ 首先，我們會問這樣的問題如何需要多長時間，這 在最壞的情況下運行的算法來？ 還記得我們代表這個運行 大O符號的時間。 為了確定最小的未分類的元素， 基本上比較列表中的每個元素 在列表中的所有其它元素。 直觀地說，這聽起來像一個O n的平方操作。 在我們的偽代碼，我們也有一個循環嵌套在 另一個循環，這的確聽起來像一個O n的平方操作。 但是，請記住，我們並不需要在 整個列表時確定的最低未分類的元素嗎？ 一旦我們知道這4排序，例如，我們沒有 需要再次來看待它。 那麼，這降低了運行時間？ 在我們的名單長度為6，我們需要把五個 比較的第一個元素，四個比較 第二個元素，依此類推。 這意味著，總的步數的總和 從1到的列表的長度減1的整數。 我們可以代表這一個總和。 我們不會進入求和。 但事實證明，這個總和是相等的n倍 N減去2比1。 或等價超過2，N的平方減去n超過2。 在談到漸近運行，這n的平方項 將主宰這n個任期。 因此，選擇排序是O n的平方。 回想一下，在我們的例子中，選擇排序仍然需要 檢查一個數字，已經排序 需要被感動。 因此，這意味著，如果我們對一個已經跑了選擇排序 排序的列表，這將需要相同數量的步驟，因為它 將運行在一個完全未排序的列表。 因此，選擇排序有最好的情況下表現為n的平方， 我們所代表的與歐米茄Ň平方。 這就是它的選擇排序。 只是其中的的算法，我們可以 使用對列表進行排序。 我的名字是湯米，這是CS50。