本課程是從少年編程網轉載的課程，目標是向中學生詳細介紹計算機比賽涉及的程式語言，數據結構和算法。編程學習最好使用計算機，請登陸 www.3dian14.org (免費註冊，免費學習)。
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據
算法介紹
插入排序最好的示例是撲克牌，很多書都以抓撲克牌的過程為例子講述插入的排序過程。
現在你需要將手牌從左到右按小到大排序。
從最左邊開始排序，最左邊1張牌是紅桃6，顯然對於1張牌而言可以看作是已經排好序（有序）的。
現在看第2張牌。
第2張牌和(已經排好序的)第1張比較, 插入到正確的位置
接下來看第3張牌。
第3張牌紅桃3依次與左邊的牌比較，找到正確的位置插入
接下來看第4張牌。
第4張牌紅桃8依次與左邊的牌比較，找到正確的位置插入
接下來看最後一張牌。
最後一張牌紅桃A依次與左邊的牌比較，找到正確的位置插入。
到這裡，排序大功告成～
動畫演示
（from Wikipedia)
算法核心思想
算法實現
沒代碼的算法都是耍流氓
顯然我們需要一個變量i來記錄每次掃描未排序部分的開頭位置。
問題終於來了。。。
答案是A。 交換2個變量值的代碼前面已經見過，就不介紹了。
和選擇排序法的比較
插入排序法和選擇排序法接近。在選擇排序法中，經過k次掃描（整個）數組，最初的k個元素完成排序。
想一想：
再想一想
不過插入排序法和選擇排序法比較，也有自身的代價：
在插入排序法中插入一個元素到已經排好序部分，該部分後右側元素都需要右移（寫操作）；而選擇排序法中每次只需要交換一對元素。
當寫操作的成本遠遠高於讀操作時，選擇排序法更優一些。
算法複雜度
讓我們考慮最好情況，最差情況， 和一般情況
最好情況 ：最好情況是數組元素已經排好序啦
During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.
Comparison/比較次數：Cmin=n-1
Move/移動次數：Mmin=0
最差情況 ： 是排好了，不過方向反了（逆序）
in these cases every iteration of the inner loop will scan and shift the entire sorted subsection 。在最壞情況下，每次都需要走過全部已經排序部分
Comparison/比較次數：Cmax=1+2+3+4+……+n-1=(n-1)n/2
Move/移動次數：Mmax=1+2+3+……+n-1=(n-1)n/2
一般情況 ： 我們用最好和最差的平均值來做粗略估計
我們做個粗略的估算，取最好情況和最壞情況的平均值來表示一般情況。在一般情況下的關鍵字比較次數和對象移動次數約為 n^2/4。因此，直接插入排序的時間複雜度為 O(n^2)。
思維導圖系列： 10大最常見排序算法
算法系列： 10大常見排序算法（1） 冒泡
算法系列： 10大常見排序算法（2） 選擇排序
請點擊閱讀原文來觀看動畫交互課件
註：部分圖片原型來自網絡。