常用12大排序算法之一:插入排序(Insert Sorting)

2017-04-20 23:17 阅读 995 次 评论 0 条

1.插入排序算法的基本思想

每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。

 

2.插入排序算法的分类

根据寻找插入位置方法分为:

(1)直接插入排序

(2)折半(二分)插入排序

(3)希尔插入排序

(4)直接插入排序

 

3.插入排序算法的具体过程

当插入第i(i≥1)个对象时,前面的V[0],V[1],…,V[i−1]已经排好序。这时,用V[i]的排序码与V[i−1],V[i−2],…,V[0]的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的对象向后顺移。

直接插入排序示意图:

直接插入排序

从上到下,分别展示了直接排序算法的所有可能的过程,包括相同排序码的排序方式(保持了原来的顺序,说明是稳定排序)以及in-place操作中的元素移动等。

直接插入排序

 

4.直接插入排序算法分析

设待排序对象个数为n,则该算法的主程序执行n−1趟排序码比较次数和对象移动次数与对象排序码的初始排列有关。

最好情况下,排序前对象已经按照要求的有序。比较次数(KCN):n−1 ; 移动次数(RMN):为0。则对应的时间复杂度为O(n)。

最坏情况下,排序前对象为要求的顺序的反序。第i趟时第i个对象必须与前面i个对象都做排序码比较,并且每做1次比较就要做1次数据移动(具体可以从下面给出的代码中看出)。比较次数(KCN):∑n−1i=1i=n(n−1)2≈n22 ; 移动次数(RMN):为∑n−1i=1i=n(n−1)2≈n22。则对应的时间复杂度为O(n2)。

如果排序记录是随机的,那么根据概率相同的原则,在平均情况下的排序码比较次数和对象移动次数约为n24,因此,直接插入排序的时间复杂度为O(n2)。

 

5.直接插入排序算法的特点

(1)它是稳定排序,不改变相同元素原来的顺序。

(2)它是in-place排序,只需要O(1)的额外内存空间。

(3)它是在线排序,可以边接收数据边排序。

(4)它跟我们牌扑克牌的方式相似。

(5)对小数据集是有效的。

 

6.插入排序C语言源代码

 

7.插入排序C++源代码

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法之一:插入排序(Insert Sorting) | 算法君

发表评论


表情