插入排序
當我們分析排序演算法的效能時，我們主要關注比較和交換的數量。
平均交換
令 E n 為 N 元素排序陣列的總平均交換次數。E 1 = 0（我們不需要對具有一個元素的陣列進行任何交換）。對 N 個元素陣列進行排序的平均交換次數是將 N-1 個元素陣列排序的平均交換次數與將最後一個元素插入 N-1 個元素陣列的平均交換次數之和。
http://i.stack.imgur.com/0I2Ba.gif
簡化求和（算術系列）
http://i.stack.imgur.com/i6vUV.gif
擴大這個詞
http://i.stack.imgur.com/qQGAc.gif
再次簡化求和（算術系列）
http://i.stack.imgur.com/D4Iye.gif
平均比較
設 C n 是與 N 元素的排序陣列的總平均比較數。C 1 = 0（我們不需要在一個元素陣列上進行任何比較）。排序 N 元素陣列的平均比較數是將 N-1 個元素陣列排序的平均比較數與將最後一個元素插入 N-1 個元素陣列的平均比較之和。如果最後一個元素是最大元素，我們只需要一個比較，如果最後一個元素是第二個最小元素，我們需要 N-1 比較。但是，如果最後一個元素是最小元素，我們不需要 N 比較。我們仍然只需要進行 N-1 比較。這就是我們在下面的等式中刪除 1 / N 的原因。
http://i.stack.imgur.com/CsWkN.gif
簡化求和（算術系列）
http://i.stack.imgur.com/V4kOL.gif
擴大這個詞
http://i.stack.imgur.com/RtUcF.gif
再次簡化求和（算術級數和諧波次數）
