Java 十大排序算法之希尔排序刨析
作者:龍弟-idea 发布时间:2021-11-16 09:27:31
标签:Java,排序算法,希尔排序
希尔排序是插入排序的一种,又称"缩小增量排序”,是插入排序算法的一种更高效的改进版本。
希尔排序原理
1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组。
2.对分好组的每一组数据完成插入排序。
3.减小增长量,最小减为1,重复第二步操作。
希尔排序的API设计
类名 | Shell |
构造方法 | Shell():创建Shell对象 |
成员方法 | 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 Shell {
//对数组a中的元素进行排序
public static void sort(Comparable[] a){
int N=a.length;
//确定增长量h的最大值
int h=1;
while(h<N/2){
h=2*h+1;
}
//当增长量h小于1,排序结束
while(h>=1){
//找到待插入的元素
for(int i=h;i<N;i++){
//a[i]就是待插入的元素
//把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中
for(int j=i;j>=h;j-=h){
//a[j]就是待插入的元素,依次和a[j-h],a[j-2h],a[j-3h]进行比较,如果a[j]小,
// 那么交换位置,如果不小于,a[j]大,则插入完成
if(greater(a[j-h],a[j])){
exchange(a,j,j-h);
}else{
break;
}
}
}
h/=2;
}
}
//比较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={9,1,2,5,7,4,8,6,3,5};
Shell.sort(a);
System.out.println(Arrays.toString(a));
}
}
测试结果:
由于增量h没有固定的值,希尔排序的时间复杂度较为复杂,但在处理大批量数据时,希尔排序的性能高于插入排序!
来源:https://blog.csdn.net/weixin_48838340/article/details/121352687
0
投稿
猜你喜欢
- SpringMVC中的 * 用于拦截控制器方法的执行,执行在Controller前后,和视图渲染完成后。如下图所示:一、创建 * 继承Han
- SharedPreferences在开发过程中,数据存取是较为频繁的,今天我们来了解下android几种常见的数据存取方式。在Android
- 一、输入输出流对象cout:标准输出流cerr:标准出凑 和cout(只是用于如果是错误时要输出的)cin :&nb
- 修改FeginCilent定义的服务名到指定服务通过覆盖类来修改对应的服务名,这里将所有的FeginClient对应的服务名都修改好。pac
- 最近在研究springboot实现FastJson解析json数据的方法,那么今天也算个学习笔记吧!添加jar包:<dependenc
- 这篇文章主要介绍了springboot 定时任务@Scheduled实现解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的
- Mybatis Log Plugin使用今天发现大部分猿友关于查看执行sql语句的方法,只知道将其输出到控制台。然而还有更简便的方法,就是使
- Class.forName(xxx.xx.xx) 返回的是一个类一.首先你要明白在java里面任何class都要装载在虚拟机上才能运行。1.
- package list;import java.util.ArrayList;/** * Java约瑟夫问题: n个人(不同id
- 部分同学在使用 idea 时可能会遇到输入 sout 无法出现自动补全 System.out.println();的情况,其实 idea 默
- 一、JdbcTemplateSpring 框架对 JDBC 进行封装,使用 JdbcTemplate 方便实现对数据库操作二、实战2.1 引
- 在分布式系统中,配置文件散落在每个项目中,难于集中管理,抑或修改了配置需要重启才能生效。下面我们使用 Spring Cloud Config
- Java8 LocalDateTime与timestamp转换将timestamp转为LocalDateTimepublic LocalDa
- 前言好久没有更新博客了,今天和大家分享一个关于emoji表情持久化问题,相信做web开发的都遇到过这样的问题,因为我们知道mysql的utf
- 导语在使用flutter 自带图片组件的过程中,大家有没有考虑过flutter是如何加载一张网络图片的? 以及对自带的图片组件我们可以做些什
- 由于工作中 使用 MultipartFile 与现有的一些上传文件组件冲突所以使用其他的接收上传文件的方法.首先我把 M
- 前言SpringBoot是我们经常使用的框架,那么你能不能针对SpringBoot实现自动配置做一个详细的介绍。如果可以的话,能不能画一下实
- 前言青空最近在逛一些社区的时候发现了有很多图片是像素图,感觉挺好玩的。正巧最近自己在学习JavaCV,所以在这里给大家演示一下如何使用Jav
- 最近有一个java实验,要求用java使用数据库,于是本人新手小白,在idea上卡了好半天希望看到这个博客的人能解决问题,跳过一些坑首先,我
- 该项目主要实现mybatisplus、多数据源、lombok、druid的集成主要参考 https://mp.baomidou.com/gu