>> [音樂播放]
>> 道格·勞埃德：所以插入排序是另一種 算法，我們可以用它來一個數組排序。
這種算法背後的想法 是建立你排序的數組
到位，換擋元件出 因為你走的路，以騰出空間。
這是稍有不同 從選擇排序或冒泡
排序，例如，其中 我們調整了位置，
我們正在做掉期交易。
>> 在這種情況下，我們實際上正在 做的是滑動元件
過，閃開。
請問這個算法 在偽代碼工作？
那麼就讓我們武斷地說， 該陣列的第一個元素是排序。
我們正在建設到位。
>> 我們會在一個時間去一個因素， 構建它，所以第一件事，我們看到
是一個元件陣列。
根據定義，一個一 元件陣列排序。
>> 然後，我們會重複這個過程until-- 我們會重複以下過程
直到所有的元素進行排序。
看看下一個未排序的元素， 將其插入到排序部，
通過移位所需數量的 元素的出路。
希望這個可視化 將幫助您看看到底是什麼
與插入排序怎麼回事。
>> 如此反复，這是我們的 整個排序的數組，
所有元素的表示為紅色。
而讓我們跟隨 步驟我們的偽代碼。
我們做的第一件事，就是我們所說的 該陣列的第一個元素，排序。
所以，我們只是會說 五，你現在來分類的。
>> 然後我們來看下 陣列的未分類的元素
我們要插入 進入排序的部分，
通過移動元素了。
所以2是下一個未排序 數組的元素。
顯然，前所屬 五，所以我們是怎麼做
是那種舉行兩場預留第二， 移5以上，然後插入兩個
前五位，哪裡應該去。
現在，我們可以說，二是排序。
>> 因此，大家可以看到，我們只是到目前為止 看著陣列的兩個元素。
我們還沒有看的 休息可言，但我們已經
得到了這兩個因素排序 變速機構的方式。
>> 因此，我們再次重複這個過程。
看看接下來的無序 元素，這是之一。
我們認為，預留第二， 轉變所做的一切，並把一隻
它應該去。
>> 同樣，還是，我們只是不斷 看了一，二，五。
我們不知道還有什麼是未來， 但我們已經分類的這三個要素。
>> 接下來排序的元素 三，因此我們將其放在一邊。
我們將通過轉移我們 需要向其中，這個時間
是不是一切如前 兩種情況下，它只是五。
然後，我們將堅持三， 兩者之間的和五個。
>> 六是下一個未排序 元件到陣列。
而事實上6大於5，所以 我們甚至不需要做任何交換。
我們可以直接釘六個直角三角形上 排序部分的端部。
>> 最後，四是 最後一個未排序的元素。
因此，我們將其放在一邊，轉移了 元素我們需要轉移過來，
然後放四個它屬於的地方。
而現在看，我們已經排序 的所有元素。
與插入通知 排序，我們沒有
去來回跨越陣列。
我們只去了整個陣列 有一次，我們轉向事物
那我們就已經遇到，為了 以騰出空間給新的元素。
>> 那麼什麼是最壞的情況下 場景與插入排序？
在最壞的情況下，該 陣列是相反的順序。
你必須改為每個n個元素 最多n個位置，每一次我們
使插入。
這是一個很大的轉變。
>> 在最好的情況下， 數組是完全排序。
而有點像發生了什麼 與在實施例5和6，
在這裡，我們可以只把它釘住 無需做任何轉換，
我們會基本上做到這一點。
>> 如果你想像我們 數組是一至六，
我們會通過開始 聲明一個排序。
二來一前一後，所以我們可以只 說好，還有一個和兩個排序。
三，三生經過兩次的話，OK， 一個，兩個和三個排序。
>> 我們沒有做任何掉期，我們 只是移動這一獨斷專行
之間的排序，排序的，因為我們去。
盡可能有效地在我們的例子中那樣， 轉彎元素的藍色，因為我們繼續。
那麼什麼是最壞的情況下運行時，又如何呢？
請記住，如果我們要轉向各 n個元素可能是N個位置，
希望這給你 一個想法，最壞的情況下
運行時間為n的大澳方。
>> 如果數組是完全 排序，所有我們需要做的
是看每一個元素 一次，然後我們就大功告成了。
因此，在最好的情況下，它是n個歐米茄。
>> 我是道格·勞埃德。
這是CS50。