总比较次数=∑j=m(n-1) 总移动次数=∑(+2)=m(n-1)+2n 平均情况下:即第趟操作,插入记录大约同前面的 个记录进行关键码比较,移动记录的次数为j/22次 总比较次数=∑ n(n ≈-n 4 4 总移动次数=∑(4+2)=1m-1)+2n=n j=1 由此,直接插入排序的时间复杂度为O(m2)。是一 个稳定的排序方法( 1) 2 1 1 1 = = − − = j n n n j j n n n n j ( 1) 2 2 1 ( 2) 1 1 = + = − + − = 总比较次数 总移动次数 平均情况下：即第j趟操作，插入记录大约同前面的j/2 个记录进行关键码比较，移动记录的次数为j/2+2次。 总比较次数 总移动次数 2 1 1 4 1 ( 1) 4 1 2 n n n j n j = = −  − = 2 1 1 4 1 ( 1) 2 4 1 2) 2 ( n n n n j n j = + = − +  − = 由此，直接插入排序的时间复杂度为O(n2 )。是一 个稳定的排序方法