雅乐网

计算机技术、学习成长

计算机 » 算法 » 插入排序

插入排序

插入排序是一种简单排序。对于少量元素的排序它很有效。

插入排序的工作方式类似于玩扑克牌抓牌时的排序

18154734-dd600b2c82ca41349e7932d9f9fccc70

此图出自算法导论2.1中插入排序插图

开始的时候左手为空,每次从桌子上拿走一张牌并把它插入到左手中正确的位置。可以从右到左依次比较。拿在左手上的牌总是有序的。

c++实现

正确性

下标j表示的是“当前牌”。在for循环的每次迭代开始 a[0]到a[j-1]的子数组构成了当前“左手上排序好的牌”。它总是有序的。我们把它称为循环不变式。

循环不变式可以用来证明算法的正确性。主要性质有

1.初始化:循环的第一次迭代之前,它为真。

2.保持:如果某次迭代之前它为真,那么下次迭代之前它仍然为真。

3.终止: 循环终止时,不变式帮助我们证明正确性。

下面看看插入排序

在算法执行的过程中,a[0]到a[i-1]始终是有序的。

1.初始化:在第一次迭代时,i等于1,a[o]到a[i-1]只包含a[0],是有序的。这表明第一次迭代之前循环不变式成立。

2.保持:第8行的for循环体将a[i]插入到合适的位置,以使a[0]到a[i]有序。

3.终止: for循环终止的时候i = n 。因此a[0]到a[n-1]的数组已经有序。

复杂度

在最糟糕的情况下,也就是序列逆序排列时,对于n-1个数中第x个数,每次将该数插入时将引起x-1次数组移动(这里不计算比较时间),求和得到 n(n-1)/2,很明显时间复杂度为O(n2)。

在已经排好序的情况下,时间复杂度为O(n)。

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/insert_sort.html

上一篇:

下一篇:

我要评论

验证码*: 8 + 6 =