Java排序算法总结之插入排序
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
本文实例讲述了Java插入排序方法。分享给大家供大家参考。具体分析如下：
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到插入排序法。本文主要介绍的是插入排序的java实现。
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。比较和交换的时间复杂度为O(n^2)，算法自适应，对于数据已基本有序的情况，时间复杂度为O(n)，算法稳定，开销很低。算法适合于数据已基本有序或者数据量小的情况。
插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置。
算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到下一位置中
6. 重复步骤2
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
代码实现
public void insertionSort() {
// 插入排序
int out, in;
int count1 = 0, count2 = 0;// 复制次数，比较次数
for (out = 1; out < nElems; out++) {
long temp = a[out];
in = out;
boolean flag=in>0&&a[in-1]>=temp;
while(flag){
if(a[in-1]>=temp){
if(in>0){
a[in]=a[in-1];
count1++;
--in;
}
}
count2++;
flag=in>0&&a[in-1]>=temp;
}
a[in] = temp;
}
System.out.println("复制次数为：" + count1 + " 比较次数为：" + count2);
}
插入排序法在数据已有一定顺序的情况下，效率较好。但如果数据无规则，则需要移动大量的数据，其效率就与冒泡排序法和选择排序法一样差了。
希望本文所述对大家的java程序设计有所帮助。
相关文章
这篇文章主要介绍了Java groovy如何提升代码运行效率,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下2020-09-09
SpringBoot快速整合SpringSecurity的详细步骤(新手都会!)
日 Spring Security 是针对Spring项目的安全框架,也是Spring Boot底层安全模块默认的技术选型,他可以实现强大的Web安全控制,下面这篇文章主要给大家介绍了关于SpringBoot快速整合SpringSecurity的详细步骤,需要的朋友可以参考下2023-03-03
当Java程序员在SQL中要写个查询语句是很简单的。但在Java里类似的语句却不容易，因为程序员不仅要反复考虑编程范式，而且也要考虑算法的问题。下面我们来看看这几个常见的错误吧2019-06-06
本文主要介绍了java接口防重提交的处理方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧2023-05-05
SpringBoot线程池和Java线程池的使用和实现原理解析
这篇文章主要介绍了SpringBoot线程池和Java线程池的用法和实现原理,本文通过实例代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下2023-04-04
本篇文章给大家分享了java模拟多线程http请求的相关实例代码，对此有需要的可以跟着测试下。2018-05-05
这篇文章主要介绍了Java中的并发工具类详细解析,CountDownLatch、 CyclicBarrier 和 Semaphore 工具类提供了一种并发流程控制的手段,Exchanger 工具类则提供了在线程间交换数据的一种手段,需要的朋友可以参考下2023-12-12
Springboot如何实现Web系统License授权认证
这篇文章主要介绍了Springboot如何实现Web系统License授权认证,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下2020-05-05
这篇文章主要介绍了Java8 新特性之日期时间对象及一些其他特性,本文给大家介绍的非常详细，具有一定的参考借鉴价值，需要的朋友可以参考下2020-01-01
下面小编就为大家带来一篇关于Java变量的声明、内存分配及初始化详解。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧2017-03-03
最新评论