java直接插入排序示例
发布时间:2021-09-27 15:53:35
影响排序效率的一般从3个方面比较:数据比较的次数,数据移动的次数,内存空间占用的大小。
我们就冒泡排序、选择排序、插入排序、快速排序做一个总的比较。一般情况下不会使用冒泡排序算法,因为它的比较次数和移动次数在几种排序算法中都是最多的,它的唯一好处是算法简单,易于理解,所以在数据量很小的时候它会有些应用价值。选择排序在比较次数上和冒泡排序一样,都是n的平方,但它把交换的次数降低到了最低,所以在数据量很小且交换数据相对于比较数据更加耗时的情况下,可以应用选择排序。
在大多数情况下,当数据量比较小或基本上有序时,插入排序算法是最好的选择。对于更大的数据量排序来说,快速排序通常是最好的方法。
上述排序算法在内存空间上占用很少,仅需要一个额外的变量来暂时存储交换时的数据项。所以在内存空间占用的大小上没有可比性。
插入排序的比较次数仍然是n的平方,但在一般情况下,它要比冒泡排序快一倍,比选择排序还要快一点。它常常被用在复杂排序算法的最后阶段,比如快速排序。
算法:经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,
使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。
首先比较L[i]和L[i-1],如果L[i-1]<=L[i],则L[1..i]已排好序,第i遍处理就结束了;
否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),
使得L[j] ≤L[j+1]时为止
优点:移动元素次数少,只需要一个辅助空间
时间复杂度n*n
当待排序记录的数量n很小时,这是一种很好的排序方法。但是n很大时,则不适
例如:int[] values = { 5, 2, 4, 1, 3 };
排序过程:
第1次:2,5,4,1,3
第2次:2,4,5,1,3
第3次:1,2,4,5,3
第4次:1,2,3,4,5
java代码:
public class InsertSort {
public static void main(String[] args) {
int[] values = { 5, 2, 4, 1, 3 };
sort(values);
for (int i = 0; i < values.length; ++i) {
System.out.println(values[i]);
}
}
public static void sort(int[] values) {
int temp;
int j = 0;
for (int i = 1; i < values.length; i++) {
if(values[i]<values[i-1])//此处的判断很重要,这里体现了插入排序比冒泡排序和选择排序快的原因。
{
temp = values[i];
//数据往后移动
for (j=i-1; j>=0 && temp<values[j]; j--)
{
values[j+1] =values[j];
}
//将数据插入到j+1位置
values[j+1] =temp;
System.out.print("第" + (i + 1) + "次:");
for (int k = 0; k < values.length; k++) {
System.out.print(values[k]+",");
}
System.out.println("");
}
}
}
}
第二个示例
package cn.cqu.coce.xutao;
public class zhijiecharu {
public static void main(String args[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
int i,j,k;
for(i=0;i<a.length;i++)
System.out.print(a[i]+"\t");
System.out.println();
for(i=1;i<a.length;i++){
for(j=i-1;j>=0;j--)
if(a[i]>a[j])
break;
if(j!=i-1){
int temp;
temp=a[i];
for(k=i-1;k>j;k--)
a[k+1]=a[k];
a[k+1]=temp;
}
}
for(i=0;i<a.length;i++)
System.out.print(a[i]+"\t");
System.out.println();
}
}
猜你喜欢
- RocketMQ 是什么Github 上关于 RocketMQ 的介绍:RcoketMQ 是一款低延迟、高可靠、可伸缩、易于使用的消息中间件
- 集合嵌套查询和集合嵌套结果的区别嵌套查询是多条sql语句分开写并配置,嵌套结果是一条sql语句关联查询并配置,实质效果是一样的。嵌套语句的查
- 利用TCP传输数据,编写客户端和服务器的程序,实现两个程序间的实时通信。在每个程序中实现了实时的发送与接收数据的功能。客户端的io界面服务器
- 本文实例为大家分享了Unity3d实现Flappy Bird的具体代码,供大家参考,具体内容如下一、小鸟在游戏中,小鸟并不做水平位移,而是通
- 在阻塞队里中,除了对元素进行增加和删除外,我们可以把元素的删除做一个延迟的处理,即使用DelayQueue的方法。本文就来和大家聊聊Java
- 日常的开发中经常会需要用到自定义View,这次刚好有个需求,需要用到带有节点的进度条。东西很简单直接继承View就行了。首先定义一些需要的属
- 在分布式系统中,配置文件散落在每个项目中,难于集中管理,抑或修改了配置需要重启才能生效。下面我们使用 Spring Cloud Config
- Spring Batch job任务只跑一次在一次实际使用spring batch的过程中,在定时任务中,第一次执行Job没有出现问题,然后
- 介绍这里学习SpringSecurity,对SpringSecurity进行学习。基本用法添加依赖<dependency> &n
- 本文实现案例场景: 某系统除了需要从自己的主要数据库上读取和管理数据外,还有一部分业务涉及到其他多个数据库,要求可以在任何方法上可以灵活指定
- 接口可以声明事件。 下面的示例演示如何在类中实现接口事件。 这些规则基本上都与实现任何接口方法或属性时的相同。在类中实现接口事件在类中声明事
- 本文实例讲述了C#动态加载dll扩展系统功能的方法。分享给大家供大家参考。具体分析如下:动态加载dll,主要是为了扩展功能,增强灵活性而实现
- Join子句一、简介使用join子句可以将来自不同源序列并且在对象模型中没有直接关系的元素相关联,唯一的要求是每个源中的元素需要共享某个可以
- Spring Cloud是一个基于Spring Boot实现的云应用开发工具,它为基于JVM的云应用开发中的配置管理、服务发现、断路器、智能
- 本文介绍了详解WMI RPC 服务器不可用的解决方案,分享给大家,具体如下:ConnectionOptions connectionOpti
- 目录I. 项目环境1. 项目依赖II. 缓存注解介绍1. @Cacheable2. @CachePut3. @CacheEvict4. @C
- BeanUtils.copyProperties无法封装使用BeanUtils.copyProperties(user, memeber);
- SSM+redis整合ssm框架之前已经搭建过了,这里不再做代码复制工作。这里主要是利用redis去做mybatis的二级缓存,mybait
- MyBatis提供了 * 接口,我们可以实现自己的 * ,将其作为一个plugin装入到SqlSessionFactory中。 首先要说的是
- @GetMapping和@GetMapping(value=““)区别背景初期对于@GetMappi