[音樂播放] 

道格·勞埃德：所以插入排序是另一種 算法，我們可以用它來一個數組排序。 這種算法背後的想法 是建立你排序的數組 到位，換擋元件出 因為你走的路，以騰出空間。 這是稍有不同 從選擇排序或冒泡 排序，例如，其中 我們調整了位置， 我們正在做掉期交易。 

在這種情況下，我們實際上正在 做的是滑動元件 過，閃開。 請問這個算法 在偽代碼工作？ 那麼就讓我們武斷地說， 該陣列的第一個元素是排序。 我們正在建設到位。 

我們會在一個時間去一個因素， 構建它，所以第一件事，我們看到 是一個元件陣列。 根據定義，一個一 元件陣列排序。 

然後，我們會重複這個過程until-- 我們會重複以下過程 直到所有的元素進行排序。 看看下一個未排序的元素， 將其插入到排序部， 通過移位所需數量的 元素的出路。 希望這個可視化 將幫助您看看到底是什麼 與插入排序怎麼回事。 

如此反复，這是我們的 整個排序的數組， 所有元素的表示為紅色。 而讓我們跟隨 步驟我們的偽代碼。 我們做的第一件事，就是我們所說的 該陣列的第一個元素，排序。 所以，我們只是會說 五，你現在來分類的。 

然後我們來看下 陣列的未分類的元素 我們要插入 進入排序的部分， 通過移動元素了。 所以2是下一個未排序 數組的元素。 顯然，前所屬 五，所以我們是怎麼做 是那種舉行兩場預留第二， 移5以上，然後插入兩個 前五位，哪裡應該去。 現在，我們可以說，二是排序。 

因此，大家可以看到，我們只是到目前為止 看著陣列的兩個元素。 我們還沒有看的 休息可言，但我們已經 得到了這兩個因素排序 變速機構的方式。 

因此，我們再次重複這個過程。 看看接下來的無序 元素，這是之一。 我們認為，預留第二， 轉變所做的一切，並把一隻 它應該去。 

同樣，還是，我們只是不斷 看了一，二，五。 我們不知道還有什麼是未來， 但我們已經分類的這三個要素。 

接下來排序的元素 三，因此我們將其放在一邊。 我們將通過轉移我們 需要向其中，這個時間 是不是一切如前 兩種情況下，它只是五。 然後，我們將堅持三， 兩者之間的和五個。 

六是下一個未排序 元件到陣列。 而事實上6大於5，所以 我們甚至不需要做任何交換。 我們可以直接釘六個直角三角形上 排序部分的端部。 

最後，四是 最後一個未排序的元素。 因此，我們將其放在一邊，轉移了 元素我們需要轉移過來， 然後放四個它屬於的地方。 而現在看，我們已經排序 的所有元素。 與插入通知 排序，我們沒有 去來回跨越陣列。 我們只去了整個陣列 有一次，我們轉向事物 那我們就已經遇到，為了 以騰出空間給新的元素。 

那麼什麼是最壞的情況下 場景與插入排序？ 在最壞的情況下，該 陣列是相反的順序。 你必須改為每個n個元素 最多n個位置，每一次我們 使插入。 這是一個很大的轉變。 

在最好的情況下， 數組是完全排序。 而有點像發生了什麼 與在實施例5和6， 在這裡，我們可以只把它釘住 無需做任何轉換， 我們會基本上做到這一點。 

如果你想像我們 數組是一至六， 我們會通過開始 聲明一個排序。 二來一前一後，所以我們可以只 說好，還有一個和兩個排序。 三，三生經過兩次的話，OK， 一個，兩個和三個排序。 

我們沒有做任何掉期，我們 只是移動這一獨斷專行 之間的排序，排序的，因為我們去。 盡可能有效地在我們的例子中那樣， 轉彎元素的藍色，因為我們繼續。 那麼什麼是最壞的情況下運行時，又如何呢？ 請記住，如果我們要轉向各 n個元素可能是N個位置， 希望這給你 一個想法，最壞的情況下 運行時間為n的大澳方。 

如果數組是完全 排序，所有我們需要做的 是看每一個元素 一次，然後我們就大功告成了。 因此，在最好的情況下，它是n個歐米茄。 

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