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


猜你喜欢
- 前言Java8 的新特性:Lambda表达式、强大的 Stream API、全新时间日期 API、ConcurrentHashMap、Met
- 记得上学的时候学习英语,每个英语老师说到英语翻译的时候都会说英语翻译要做到“信、达、雅”。如今做了一名程序员竟然体会我还是想用这三种境界来要
- 在springboot项目中如果要在不集成templates的情况下访问静态资源需要做以下配置1.在项目的application.yml文件
- 本文实例为大家分享了基于servlet实现统计网页访问次数的具体代码,供大家参考,具体内容如下一、基础知识(1)ServletContext
- SpringBoot启动自动终止也不报错Error starting ApplicationContext. To display the
- 由于Android课程项目需要,特地查阅了okHttp的使用,发现网上找的大多和自己的需求不一样。所以就着团队项目需要,自己简单封装了一个o
- 先讲一下java中的反射:反射就是将类别的各个组成部分进行剖析,可以得到每个组成部分,就可以对每一部分进行操作反射机制应用场景:逆向代码、动
- 效果图如下所示:一、shape 样式:(在drawable新建--》new--》Drawable resource file 在父级标签se
- 前言SQL注入漏洞作为WEB安全的最常见的漏洞之一,在java中随着预编译与各种ORM框架的使用,注入问题也越来越少。新手代码审计者往往对J
- 分页问题是一个非常普遍的问题,开发者几乎都会遇到,这里不讨论具体如何分页,说明一下Web方式下分页的原理。首先是查询获得一个结果集(表现为查
- 简述mysq5.7之后新增了json类型,但是在使用的过程中,Json数组中的值小于Integer.MAX_VALUE,则反序列化时会转成L
- web 容器的设计开发一个web容器涉及很多不同方面不同层面的技术,例如通信层的知识,程序语言层面的知识等等,且一个可用的web容器是一个比
- 将二维数组转化为一维数组1. 为了偷懒所以我写了一个随机生成二维数组的函数/* * 自动创建随机为100以内的二维
- 一.简单介绍1.配置相关的依赖2.配置模式3写.mapper、controller、service4.配置yaml文件 配置mybatis全
- 简介上一篇我们介绍了在android里如何读写本地文件。我们有一种场景,类似网页的cookie,要把用户的一些储如上一次登录、使用的痕迹等信
- 配置Servlet的方法有俩种,分别是传统web.xml文档中部署servlet和注解方式部署servlet,下面就先一起来学习 * 解方式部
- SpringMVC异常处理机制(一)项目前准备首先参照文章Spring课程工程构建+SpringMVC简介及其快速入门搭建项目搭建好一个项目
- 1、使用步骤1)构建请求网址A、确定端点:每个GIS服务都有一个端点。例如,ArcGIS Server上Demographics文件夹下名为
- 今天学习到sql中的ResultSet,用到了获取总函数,网上百度说是使用getRow()方法,但是一值返回0.后台调试才发现getRow(
- zookeeper集群配置多个实例共同构成一个集群对外提供服务以达到水平扩展的目的,每个服务器上的数据是相同的,每一个服务器均可以对外提供读