插入排序也是一类非常常见的排序方法,它主要包含直接插入排序,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).
直接插入排序是稳定的.