Tip:
Highlight text to annotate it
X
這段影片中我想探討某種
我認爲更直觀的排序方法
若我必須手工排序則多半會這麽做
但我想澄清的是
這不是最高效的排序方式
咱們就先
我認爲這是個好的開頭
咱們可以由此爲排序先熱熱身
該方法叫做插入排序
我將給出圖形化的說明
來解釋插入排序算法
你要知道
算法聽起來像個神奇的詞
但某個算法其實只是排序的一種手段
一個過程
或一種方法
程序則是特定算法的具體實現
或者可以成爲某個算法的具體實現
一旦我有一個一般的算法,
我可以用 Python 實現
可以用 C 實現
用 Java 實現
這些都是具體的程序
但它們都是實現了
同一種排序方式
這就是我所說的
插入排序算法
咱們從一個簡單的例子開始
咱們假設我有一個列表
假設我有一個 Python 的列表
因爲我們將用 Python 實現該算法
該列表是
咱們說它是 [7,3,1,2,4,6]
所以我們做插入排序的方式
就是依次檢查每個元素
將其與前邊的元素進行比較
當你找到它前面第一個比它小的元素
當你找到它前面第一個比它小的元素
你就把它固定在那個位置
還是讓我來示範一下剛說的
你可以從7入手
這裡的第0個元素
但當你審視
當你從第0個元素開始時
你會發現 等一下 它前邊沒有東西可以比
所以從第0個元素開始沒有意義
說真的 如果你要實現這個算法
你最好從第[1]個元素開始
抱歉 你從
如果這是第0個元素
你從這裡的第1個元素開始
這是第0個 這是第1個 我很清楚
但如果你把它當成第1個元素 你會很困惑
它其實是第0個
所以你從這裡的3開始
你開始將它與它之前的所有元素進行比較
一旦發現首個比3大的元素
你就把它固定在列表的這個部分
所以你的做法是說
好的 3少於7嗎
是的 少於 7
所以你所要做的就是交換
把7換到3的位置
我來把它放在這兒
我們正在
我們正試著將3和它之前的所有元素進行比較
我們正試著將3和它之前的所有元素進行比較
所以你說 好的 3比7小嗎
是啊 它少於7
所以咱們把7放在3的位置
把3放在7的位置
因爲左邊沒剩下其他元素可以與3比較
前面沒有更多
第0個元素之前沒有元素了
所以咱們把3就固定在那兒
所以我們的列表現在看起來像這樣
我們的列表現在看上去是[3,7,1,2,4,6]
你會發現一件有趣的事
有些地方需要注意
在我們生成這個列表的時候
現在第0個元素肯定少於第1個
從開頭到包括第1個元素在內的所有元素
已經是有序的了
從開頭到包括第1個元素在內的所有元素
已經是有序的了
這一特點將會一直成立 隨著我們繼續進行
所這我們處理下標更加靠後的元素
一直到包括該下標元素在內的所有元素
在我們完成這一趟排序後 都將是有序的
在繼續進行過程中 我會試著指出這一點
我們處理過了第1個下標
現在可以繼續處理第2個元素
也就是這個1
於是你把這個1
我會把它放在一邊
你提出這個1
並將其與它之前的每一個元素比較
1比7小嗎
當然 1少於7
所以咱們把7固定在1那兒
然後你既可以繼續比較下一個元素
或者你可以只把1固定在7的位置
然後繼續比較 1少於3嗎
肯定啊 它是少於 3
所以咱們將3固定在1那兒
之後咱們把1放到3的位置
那麽現在我們的列表什麽樣了
我們的列表現在看起來
我們的列表現在是[1,3,7,2,4,6]
注意 在我們到達第 n 個索引後
在這種情況下是索引 2
也就是 1 先前所在的地方
從頭開始包括該索引的每個元素已經有序
這裡的這部分已經有序
它會是
隨著我們繼續 其他的元素都將會加入這裡
隨著我們繼續 其他的元素都將會加入這裡
但目前爲止這部分已經有序了
所以你可以看到
當我們到達列表結尾的時候
一切都會排列爲有序
那咱們來處理下一個索引
或者說是列表中的下一項
也就是這裡的2
也就是這裡的2
所以我們拿2和7比
2 肯定少於 7
所以咱們把 7 放在 2 那兒
把 2 放在 7 那兒
現在比較 2 和 3
2 少於 3
咱們就把 3 放在 2 的位置
並且把 2 放在 3 的位置
然後比較 2 和 1
2 比 1 小嗎
它並不少於 1
所以我們不需要做什麽
我們不必繼續往左邊考察了
所以在現在這一趟排序之後
在此階段我們用 2 這一項
與它之前的所有元素比較
所以在這趟排序之後 我們的列表看起來像這樣
我們的列表看起來像[1,2,3,7,4,6]
我注意到 從左開始 包括第3項在內的所有元素
第 0 1 2 3 個項
現在已經有序
現在我們準備看看這個
列表中的下一個元素
我想澄清一件事
當你真正實現它的時候
有多種方法來做
你不用總是
在此示例中 我們說
嘿 2 是少於 7 嗎
7 取代了 2 的位置
像你本來就應該做的
然後我們讓 2 取代了 7 的位置
但現實是
你可以一直向左
直到你找到適合 2 的好位置
然後把其他元素移到右邊
然後把 2 放進去
盡管咱們的方式更容易理解
也許我們將探索不同的方法來做這件事
當我們實際實現本算法時
好了 咱們看看這個 4
完全一致的理念
4 少於 7
所以咱們把 7 放在 4 的位置
把 4 放在 7 那兒
4 比 3 小嗎
4 不少於 3
所以咱們完成了
現在 包括第 4 項在內的前邊所有元素
在列表中的第 0 1 2 3 4 項
現在已經有序
現在我們的列表看起來像
讓我向下滾動一點
我們的列表看起來像這樣
你把它寫下來
它是[1,2,3,4,7,6]
現在我們可以轉到此列表中的最後一個元素
這是我們現在正在比較的 6
這是我們最後一次進行比較
就像之前針對 4 所做的
但現在我們關注 6
6 比 7 小嗎 肯定的
所以咱們把 7 放在 6 的位置
把 6 放在 7 那兒
6 比 4 小嗎 並非如此
於是我們停住
因爲我們知道排序將要完成
如果我們還要往前找 我們只會得到不大於4的元素
我們只會得到不大於4的元素
所以我們完成了 我們已對此列表排序完畢
排序後的列表現在是[1,2,3,4,6,7]
在下一個影片中
我其實要嘗試實現
我剛剛描述的這種算法
我用一個簡單的 Python 函數實現它