[Powered by Google Translate] [插入排序]
[和湯米MacWilliam] [哈佛大學]
[這是CS50.TV]
讓我們來看看插入排序，算法的號碼列表和排序。
簡單的算法，記住，是一步一步的過程來完成任務。
後面插入排序的基本思想，是將我們的名單分為兩部分，
一個的排序部分和未排序的部分。
>> 該算法在每個步驟中，一個數字移動
在未排序的部分排序的部分
直到最後整個列表進行排序。
這裡是六個未排序的數字列表 - 23，42，4，16，8，和15。
因為這些數字是不是所有的升序排列，它們排序。
因為我們還沒有開始整理，我們會考慮所有的六大要素，我們未分類的部分。
>> 一旦我們開始整理，我們把這些排序的數字，剩下的這些。
所以，讓我們開始有23個，在列表中的第一個元素。
我們沒有尚未我們的排序部中的任何元素，
讓我們簡單地認為23是我們的排序部分的開始和結束的。
現在，我們的排序部分有一個數字，23，
我們未分類的部分有這五個數字。
現在讓我們插入到我們的未分類的部分，42歲，在未來數排序的部分。
>> 要做到這一點，我們需要比較的42到23 - 到目前為止，我們的排序部分中的唯一元素。
四是大於23，所以我們可以簡單地追加42月底
的排序的列表中的部分。太好了！
現在，我們的排序部分也有兩個元素，我們未分類的部分有四個元素。
所以，現在讓我們轉移到了4，未排序的部分中的下一個元素。
所以，這應該被放置在排序部？
>> 請記住，我們想要把這個數的排序順序
因此，在任何時候，我們的排序部分保持正確排序。
如果我們把4個到42個的權利，那麼我們的名單將出。
所以，讓我們繼續在我們的排序部分從右到左移動。
隨著我們的，讓我們每個號碼轉移下來的地方以騰出空間給新的號碼。
好了，4也是小於23，因此，我們不能把它在這裡。
讓我們繼續前進的23個正確的地方。
>> 這意味著我們想放置4到第一個插槽的排序部分。
請注意，這個空間是如何在列表中已經是空的，
因為我們一直在移動排序的元素，因為我們已經遇到他們。
好的。因此，我們已經完成一半了。
讓我們繼續我們的算法插入16到排序的部分。
16為小於42，所以讓我們轉移42至正確的。
16為小於23，所以我們也該元素的轉移。
>> 現在，圖16是大於4。因此，它看起來像我們想在4和23之間插入16。
通過排序的列表部移動的同時，由右至左，
4是第一個數字，我們已經看到，數小於
我們正在試圖插入。
所以，現在我們可以插入16到這個空的插槽，
請記得，我們​​已經創建了移動的元素在排序部分
我們遇到他們。
>> 好的。現在，我們有四個排序的元素和兩個未排序的元素。
所以，讓我們繼續前進8成排序的部分。
八是小於42。
八是小於23。
和圖8是小於16。
但是，圖8是大於4。
所以，我們想在4和16之間插入8。
現在，我們只是有一個更多的元素進行排序 - 15。
十五是小於42，
十五是小於23。
和15是小於16。
但15是大於8。
>> 所以，在這裡我們想使我們的最後插入。
我們就大功告成了。
我們有沒有更多的元素在未排序的部分，
和我們的排序條件部分是在以正確的順序。
從最小到最大的數字是有序的。
所以，讓我們來看看一些偽代碼描述的步驟，我們只是執行。
>> 在第1行中，我們可以看到，我們需要遍歷列表中的每個元素
除了第一個，因為第一個元素在未排序的部分，都只是
的排序部中的第一元素。
在第2和第3行，我們正在跟踪我們目前在未排序的部分。
元素代表的數量，我們目前正在進入排序的部分，
j表示我們的索引中未排序的部分。
>> 在第4行中，我們遍歷由右至左排序的部分。
我們要停止迭代一次的元素的左側我們當前的位置
是小於我們試圖插入的元素。
在第5行中，我們把每一個元素我們遇到的一個空間，以正確的。
這樣一來，當我們找到的第一個元素，我們將有一個明確的空間插入到
不到我們正在元素。
在第6行，我們正在更新我們的櫃檯，繼續向左移動通過排序的部分。
最後，第7行，我們的元素插入到列表中的排序部分。
>> 我們知道它的好插入位置j，
因為我們已經提出的元素，以前是有一個空格的右側。
請記住，我們正在通過由右至左排序的部分，
但我們正在通過未排序的部分由左到右。
好的。現在，讓我們來看看在多長時間運行的算法了。
多久需要運行這個算法在最壞的情況下，我們首先會問的問題。
回想一下，我們與大O表示法表示這個運行時間。
為了我們的列表進行排序，我們不得不遍歷未排序的部分中的元素，
並為每個這些元素，可能超過的排序部中的所有元素的。
直觀地說，這聽起來像一個O（N ^ 2）操作。
>> 在我們的偽代碼，我們有一個循環嵌套在另一個循環，
而事實上，聽起來像一個O（N ^ 2）操作。
然而，排序的部分列表中沒有包含整個列表，直到最後一刻。
儘管如此，我們可能在開始的時候排序的部分中插入一個新元素
在每次迭代的算法，
這意味著我們不得不看每個元素目前在已排序的部分。
所以，這意味著我們有可能做一個比較的第二個元素，
兩個比較的第三個元素，依此類推。
所以，總的步數是從1到的列表的長度減1的整數的總和。
我們可以代表這一個總和。
>> 在這裡，我們不會去求和，但事實證明，這個總和是相等的
超過2 N（n - 1個），這相當於n ^ 2的/ 2 - n / 2個。
在談到關於漸近運行時，
這n ^ 2項將主宰這n個任期。
所以，插入排序是大O（N ^ 2）。
如果我們遇到一個已排序的列表中插入排序。
在這種情況下，我們只需要建立從左至右排序的部分。
所以，我們只需要n個步驟的順序。
>> 這意味著，插入排序的n有一個最好的情況下的性能，
我們與Ω（n）的代表。
這就是它插入排序，
只是我們的許多算法可以對列表進行排序。
我的名字是湯米，這是CS50。
[CS50.TV]
啊，你只是不能停止，一旦它開始。
哦，我們這樣做 - “”轟！“