算法的思想就是将数组分成两部分，左側部分是已经排序好的，右側部分是不可见的状态。每次取出右側中的一个元素，放到左側的最右边，然后不断向左移动，直到遇到较小的元素为止。

动画

命题

插入排序平均情况下大约运行1/4 N^2次比較和1/4 N^2次交换。

最佳情况

对于已经排序好的数组仅仅需验证是否排序就可以，须要N-1次比較，0次交换。

最坏情况

对于反序数组，插入排序须要1/2 N^2次比較和1/2 N^2次交换

部排序的数组

命题

对于部分排序的数组，插入排序的执行时间是线性的。

数据交换的次数等同于反序次数。

比方1 3 2 4 6 5中3和2顺序是相反的，6和5顺序是相反的，因此反序次数是2

动画

代码

public 

class 

Insertion {

    

public 

static 

void 

sort(Comparable[] li) {

        

for

(

int 

i = 

0

; i < li.length; i++) {

            

for

(

int 

j = i; j > 

0

; j--) {

                

if

(SortUtil.less(li[j], li[j-

1

])){

                    

SortUtil.exch(li, j, j-

1

);

                

} 

else 

{

                    

break

;

                

}

            

}

        

}

    

}

}

第5行：比較的是li[j]和li[j-1]而不是li[j]和li[i]