插入排序
当我们分析排序算法的性能时，我们主要关注比较和交换的数量。
平均交换
令 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
再次简化求和（算术级数和谐波次数）
