插入排序也是一类非常常见的排序方法,它主要包含直接插入排序,Shell排序和折半插入排序等几种常见的排序方法.

1.直接插入排序

直接插入排序的思路非常简单:依次将待排序的数据元素按其关键字值的大小插入前面的有序序列.

细化来说:对于一个有n个元素的数据序列,排序需要进行n-1趟插入操作,如下所示:]

第1趟插入:将第2个元素插入前面的有序子序列中,此时前面只有一个元素,当然是有序的.

第2趟插入:将第3个元素插入前面的有序子序列中,前面两个元素是有序的.

......

第n-1趟插入:将第n个元素插入前面的有序子序列中,前面n-1个元素是有序的.

掌握了上面的排序思路之后,如下程序实现了直接插入排序:

上代码:

 

运行上面的程序,下面显示了直接插入排序的执行过程.

直接插入排序的时间效率并不高,在最坏的情况下,所有元素的比较次数总和为(0+1+....+n-1)=O(n*n);

在其他情况下,也要考虑移动元素的次数,故时间复杂度为O(n*n).

直接插入排序的空间效率很好,它只需要一个缓存数据单元.也就是说,空间效率为O(1).

直接插入排序是稳定的.