插入排序的Java代码实现

发布时间:2017-7-9 7:05:38编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"插入排序的Java代码实现 ",主要涉及到插入排序的Java代码实现 方面的内容,对于插入排序的Java代码实现 感兴趣的同学可以参考一下。

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

直接插入排序是稳定的.


上一篇:debug-stripped.ap_' specified for property 'resourceFile' does not exist.(转载)
下一篇:剑指Offer——旋转数组的最小数字

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款