排序算法(5)——插入排序

2、插入排序的性能

1）、时间复杂度 最差时间复杂度为 O(n^2)。当数据是逆序的，比较次数和交换次数都是1+2+3+…i+…(n-1)，即n*(n-1)/2。 最好时间复杂度是O(n)。当数据是已经排好序的,这时内层的for检测总是判定不成立的。 平均时间复杂度为 O(n^2)。因为平均时间复杂度接近于最差时间复杂度。

2）、稳定性 插入排序是稳定的排序算法。因为它是从右往左找合适的（不大于它）位置，再进行插入，所以即便有两个相等的元素，经过排序，前后还关系依旧维持。

和其它层算法的比较： 插入排序和冒泡排序都是稳定的排序。