Java 十大排序算法之插入排序刨析
作者:龍弟-idea 时间:2021-12-07 02:48:54
插入排序原理
①把所有元素分成已排序和未排序两组
②找到未排序组的第一个元素,向已经排序的组中进行插入
③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位
插入排序API设计
类名 | Insertion |
构造方法 | Insertion():创建Insertion对象 |
成员方法 | 1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exchange(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值 |
插入排序代码实现
public class Insertion {
//对数组a的元素进行排序
public static void sort(Comparable[] a){
for(int i=1;i<a.length;i++){
//当前元素为a[i],依次和i前面的元素比较,找到一个小于等于a[i]的元素
for(int j=i;j>0;j--){
if(greater(a[j-1],a[j])){
exchange(a,j-1,j);
}else{
//找到了该元素,结束
break;
}
}
}
}
//比较v元素是否大于w元素
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
//数组元素i和j交换位置
private static void exchange(Comparable[] a,int i,int j){
Comparable t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//测试代码
class Test{
public static void main(String[] args) {
Integer[] a={4,3,2,10,12,1,5,6};
Insertion.sort(a);
System.out.println(Arrays.toString(a));
}
}
运行结果:
插入排序的时间复杂度分析
和冒泡排序分析相同!
虽然使用了双层循环,但内循环是真正完成排序的代码,所以主要分析内层循环的执行次数即可!
在数组元素为{12,10,6,5,4,3,2,1}为最坏情况
元素的比较次数为:(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
元素的交换次数为:(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
总执行次数为:2*(N^2/2-N/2)=N^2-N;
根据大O推导法则,保留最高阶项,即插入排序的时间复杂度为O(N^2)
来源:https://blog.csdn.net/weixin_48838340/article/details/121349084
标签:Java,插入排序,排序算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
java简易小游戏制作代码
2023-11-23 19:49:38
![](https://img.aspxhome.com/file/2023/8/59048_0s.jpg)
Java文本文件操作方法实例详解
2021-12-14 10:03:21
教你怎么在IDEA中创建java多模块项目
2023-05-28 19:25:58
![](https://img.aspxhome.com/file/2023/9/65199_0s.png)
Java后端学习精华之TCP通信传输协议详解
2021-08-06 03:15:42
![](https://img.aspxhome.com/file/2023/1/64221_0s.png)
Java实现树形List与扁平List互转的示例代码
2023-03-15 00:18:23
Java继承Thread类创建线程类示例
2023-08-04 20:27:08
在spring中手写全局异常拦 截器
2023-11-09 01:25:42
Spring Boot整合Web项目常用功能详解
2023-06-04 17:14:21
详解SpringMVC常用注解功能及属性
2021-12-29 02:49:23
Java实现简单班级管理系统
2023-01-07 16:20:29
![](https://img.aspxhome.com/file/2023/0/66630_0s.jpg)
IDEA的Swing可视化插件JFormDesigner详解
2023-09-23 08:02:54
![](https://img.aspxhome.com/file/2023/6/62996_0s.jpg)
java实现纸牌游戏之小猫钓鱼算法
2021-08-11 22:57:00
SpringBoot深入了解日志的使用
2023-01-06 15:40:34
![](https://img.aspxhome.com/file/2023/7/65177_0s.png)
java中的数组初始化赋初值方式
2021-11-23 03:08:37
详解Java的回调机制
2023-07-27 07:17:43
![](https://img.aspxhome.com/file/2023/7/60657_0s.png)
浅谈hibernate急迫加载问题(多重外键关联)
2023-08-18 12:58:54
![](https://img.aspxhome.com/file/2023/2/65202_0s.png)
Java设计模式之备忘录模式
2023-08-24 06:17:05
SpringBoot整合Redis之编写RedisConfig
2023-08-29 02:35:57
Spring 应用中集成 Apache Shiro的方法
2023-02-18 05:44:55
springboot使用Mybatis-plus分页插件的案例详解
2023-10-27 13:47:43