Java经典排序算法之插入排序
作者:欧阳鹏 发布时间:2022-08-29 11:08:39
一、算法原理
插入排序法:所谓插入排序法乃是将一个数目插入该占据的位置。
假设我们输入的是 “53,27,36,15,69, 42” 我们从第二个数字开始,这个数字是27,我们的任务只要看看27有没有正确的位置,我们的做法是和这个数字左边的数字来比,因此我们比较27和53,27比53小,所以我们就交换27和53,原来的排列就变成了“27, 53, 36, 15, 69, 42 ”
接下来,我们看第3个数字有没有在正确的位置。这个数字是36,它的左边数字是53,36比53小,所以我们将36和53交换,排列变成了 “27,36, 53, 15, 69, 42 "我们必须继续看36有没有在正确的位置,36的左边是27,27比36小,36就维持不动了,这时候排序还是“27, 36, 53, 15, 69, 42 "。
再来看第四个数字,这个数字是15,我们将15和它左边的数字相比,都比15大,所以就将15一路往左移动,这时候排序变成了 “15, 27, 36, 53, 69, 42 ”。
再来看第五个数字,这个数字是69,我们将69和它左边的数字相比,都比69小,所以就69维持不动了,这时候排序变成了 “15, 27, 36, 53, 69, 42 ”
最后,我们检查第六个数字,这个数字是42,42必须往左移,一直移到42的左边是36为止,所以我们的排列就变成了 “15, 27, 36, 42 ,53, 69”排序因此完成了。
ps:读者也可以自己打开下面的链接,自己设定要排序的数组,进行排序演练
直接插入排序动画演示
所谓插入排序法,就是检查第i个数字,如果在它的左边的数字比它大,进行交换,这个动作一直继续下去,直到这个数字的左边数字比它还要小,就可以停止了。插入排序法主要的回圈有两个变数:i和j,每一次执行这个回圈,就会将第i个数字放到左边恰当的位置去。
二、算法描述
1、从第一个元素开始,该元素可以认为已经被排序。
2、取出下一个元素,在已经排序的元素序列中从后向前扫描。
3、如果该元素(已排序)大于新元素,则将该元素移到下一位置。
4、重复步骤3,直到找到已排序的元素小于或者大于新元素的位置。
5、将新元素插入到该位置。
6、重复步骤2。
三、效率分析
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况如下。
最好情况:序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。
最坏情况:序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。
直接插入排序属于稳定的排序,最坏时间复杂度为O(n^2),最好时间复杂度为O(n),空间复杂度为O(1)。
插入排序的赋值操作是比较操作的次数加上(n-1)次。
因此,插入排序不适合对于数据量比较大的排序应用。
四、代码实现
public class InsertSortTest {
public static void InsertSort(int[] source) {
int i, j;
int insertNode;// 要插入的数据
// 从数组的第二个元素开始循环将数组中的元素插入
for (i = 1; i < source.length; i++) {
// 设置数组中的第2个元素为第一次循环要插入的数据
insertNode = source[i];
j = i - 1;
// 如果要插入的元素小于第j个元素,就将第j个元素向后移
while ((j >= 0) && insertNode < source[j]) {
source[j + 1] = source[j];
j--;
}
// 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
source[j + 1] = insertNode;
System.out.print("第" + i + "趟排序:");
printArray(source);
}
}
private static void printArray(int[] source) {
for (int i = 0; i < source.length; i++) {
System.out.print("\t" + source[i]);
}
System.out.println();
}
public static void main(String[] args) {
int source[] = new int[] { 53, 27, 36, 15, 69, 42 };
System.out.print("初始关键字:");
printArray(source);
System.out.println("");
InsertSort(source);
System.out.print("\n\n排序后结果:");
printArray(source);
}
}
五、运行结果
初始关键字: 53 27 36 15 69 42
第1趟排序: 27 53 36 15 69 42
第2趟排序: 27 36 53 15 69 42
第3趟排序: 15 27 36 53 69 42
第4趟排序: 15 27 36 53 69 42
第5趟排序: 15 27 36 42 53 69
排序后结果: 15 27 36 42 53 69
来源:http://blog.csdn.net/ouyang_peng/article/details/46547091
猜你喜欢
- 概述Spring boot 中的 @Conditional 注解是一个不太常用到的注解,但确实非常的有用,我们知道 Spring Boot
- dom4j是一个非常优秀的Java XML API,具有性能优异、功能强大和极端易用使用的特点,同时它也是一个开放源工具。可以在这个地址ht
- 作者:京东零售 张宾1.背景在后台开发中,会经常用到线程池技术,对于线程池核心参数的配置很大程度上依靠经验。然而,由于系统运行过程中存在的不
- 调用SAP WebService服务需要转换操作1、通过浏览器访问SAP WebService地址,进行验证并生成wsdl文件地址并不是可以
- RabbitMQ作为AMQP的代表性产品,在项目中大量使用。结合现在主流的spring boot,极大简化了开发过程中所涉及到的消息通信问题
- 本文介绍C#编程时,给定一个字符串,如何判断它是不是一个日期。本文将介绍两种方法,一个是判断字符串是否是时间,如果是就转换为一个时间变量,第
- Java包装类基本类型大小包装器类型boolean/Booleanchar16bitBooleanbyte8bitByteshort/16b
- 一、前言最近接到一个任务,需要爬取五级行政区划的所有数据(大概71万条数据在),需要爬取的网站:行政区划 - 行政区划代码查询 发
- 我们知道二维数组,是在一维数组的基础上进行了维度的增加。那么在实际使用的过程中,有时候我们所需要的二维数组,它们其中的维度是不同的,这就需要
- MyBatis一对多的xml配置用的是window上面的画图板,没法以文字的方式展示出来,见谅嵌套查询嵌套结果一对多关联查询xml配置写法
- 介绍前面一章说了AbstractApplicationContext中的refresh方法中的invokeBeanFactoryPostPr
- 1 简介之前我们在文章《K8ssandra入门-详细记录在Linux上部署K8ssandra到Kubernetes》成功地在Ubuntu上安
- 一、概述定义一个值类型,其中包含固定值集合。枚举类型变量可以是此集合中的任意一个或多个值。枚举使用enum关键字来声明,与类同级。枚举本身可
- 1. 前言Spring最重要的一个概念当属Bean了,我们写的Controller、Service、Dao凡是加了对应注解交给Spring管
- 本文实例讲述了Java删除二叉搜索树最大元素和最小元素的方法。分享给大家供大家参考,具体如下:在前面一篇《Java二叉搜索树遍历操作》中完成
- 概述在移动应用开发中,消息推送可以说是一项非常重要的功能,它能够起到提醒或者唤醒用户的作用,同时也是产品运营人员更高效地实现运营目标的重要手
- 今天有朋友问我一道面试题,有5个人抢5个红包,可重复抢,用多线程程序实现,实现方式有多种,分享一下我的思路:应用了阻塞队列的特性。/**
- 简介备忘录设计模式(Memento Design Pattern)也叫作快照(Snapshot)模式,主要用于实现防丢失、撤销、恢复等功能。
- 上一篇JavaMail入门第四篇 接收邮件中,控制台打印出的内容,我们无法阅读,其实,让我们自己来解析一封复杂的邮件是很不容易的,邮件里面格
- c#开发cad如何预览图块1.定义变量的方法代码如下2. 获取GetDwgImag图像的方法代码3.实现显示DWG文件的方法代码方