上次有朋友問最近這些算法的文章受眾是什麼樣的人？其實受眾還是挺廣泛的。有要打比賽的小學高年級到中學的學霸，以及各位願意參與孩子學習的學霸家長；有大學計算機的學生；有準備考計算機研究生的人員；也可以是在職的程序員朋友；還有教編程的老師等等。
1插入排序的邏輯
我們剛剛看完了冒泡排序和選擇排序，今天再學習一下插入排序，依然是用之前的題目, 這樣排列的6個數字。
通過插入排序，把這6個數字按照從左到右從小到大的順序排列好，也就是目標是這樣的：
插入排序的邏輯是假設這些數字中有一個有序的列表，然後不斷往這個列表裡插入新的數字。類似下圖：
那一開始，我們也不知道這些數字當中有沒有有序的列表怎麼辦？其實一開始只要把第一個數字作為有序的列表就可以，因為一個數字肯定是有序的。而後只要把右邊其他數字依次插入到這個有序列表就可以。
下圖中我們用兩個紅色豎線 框起來的數字是一個有序的列表，每次拿有序列表右側的一個數字與有序列表當中的數字倒序進行比較，紅色的線段是代表比較的，比較之後根據情況插入。
下面我們拆解一下具體執行步驟：
第一步，我們用5和有序列表中唯一的數字8進行比較，5比8小，所以把5挪到8前面，8向後挪動一位。
第二步，用3和有序列表中最後一個數字8進行比較，3比8小，接著把3和8前面數字5進行比較，3比5小，所以把3挪到5前面，5和8向後挪動一位。
第三步，用6和有序列表中最後一個數字8進行比較，6比8小，繼續用6和5比較，5比6小，所以把6挪到8前面，8向後挪動一位。
......
2一個疑問
大家可能有個疑問，為什麼是倒序（從右到左）比較，比如第二步中為什麼是3先和8比較，再和5比較，為什麼不從左到右進行比較，先比較5，再比較8？
大家可以設想一下兩個極端情況：
這個列表一上來就是完全有序的這種情況如果用倒序比較，每次每個數字只需要比較一次，這樣只需要比較n-1次，n是列表數量。不需要任何移動。
這個列表一上來是逆序排列的這種情況如果用倒序比較，第一次比較1次，移動1個元素（不考慮有序列表右側元素的插入），第二次比較2次，移動2個元素，... 第n-1次比較n-1次，移動n-1個元素，所以一共比較移動了n(n-1)/2+n(n-1)/2=n(n-1)次，再加上每次有序列表右側元素的插入操作，共2(n-1)次，所以就是n(n-1)+2(n-1)=n(n+1)-2次，總得來說與n2成正比。
所以逆序排列的情況用正序比較，也就是每次只需比較一次，比較次數從原來的n(n-1)/2降到n-1次，但是移動次數不變。實際上遇到純逆序的情況，我們一般也不會選擇插入排序，會有更好的替代方法，所以我們的插入排序時就用倒序比較。
3編程實現
完整代碼如下：
下面再拆解下代碼是如何做出來的：
1.插入排序時分成兩部分數據，一部分是有序列表，一部分是有序列表右邊的數據。
我們可以把有序列表右邊第一位作為分界點，定義個變量i代表這個分界點。
然後我們的任務就是要去找有序列表當中的插入點來插入分界點的數據。下面這一步就是尋找插入點的代碼片段，這段代碼運行後變量j就是插入點。
2. 在插入點將分界點元素插入，插入點之後的所有元素後移一位。
3. 1，2兩段代碼組合就完成了一次比較和插入。之後循環對有序列表右側所有元素進行處理就可以達成我們的最終目的，也就是開頭的完整代碼。
3總結
插入排序看起來也不難理解，現在我們已經寫完了早期的三大排序算法，冒泡，選擇和插入。究竟該選擇哪種排序算法呢？我將在明天的推文裡揭曉答案。
