专栏首页码字搬砖排序算法之希尔排序-Java版

排序算法之希尔排序-Java版

1. 希尔排序

1.1 希尔排序的基本介绍

希尔排序是加强版的插入排序,相对与普通的插入排序做了优化,比普通的插入排序多了一个步长的概念

1.2 希尔排序思想

就是把数据下标按照一定的步长进行分组,然后每组分别用普通插入排序进行排序,知道步长减至为 1 时,算法终止。

1.3 希尔排序的时间复杂度和空间复杂度等

算法名称

平均时间复杂度

最好情况

最坏情况

空间复杂度

稳定性

希尔排序

O(nlogn)

O(nlogn)

O(nlogn)

O(1)

不稳定

2. 代码演示

/**
 * @author shengjk1
 * @date 2020/4/9
 */
public class ShellSort {
	public static void main(String[] args) {
		int[] arr = {1, -2, 2, -3, 5, 0};
		
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			
			for (int j = gap; j < arr.length; j += gap) {
				int insertIndex = j;
				int insertValue = arr[insertIndex];
				
				while (insertIndex - gap >= 0 && arr[insertIndex - gap] > insertValue) {
					arr[insertIndex] = arr[insertIndex - gap];
					insertIndex -= gap;
				}
				arr[insertIndex] = insertValue;
				System.out.printf("第%d次遍历 insertIndex %d arr:%s", j, insertIndex, Arrays.toString(arr));
				System.out.println();
			}
		}
	}
}

代码基本与普通插入排序一致。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序算法之插入排序-java版

    将待排序的数组看成一个有序列表和一个无序列表。刚开始时有序列表只有一个元素 arr[0],无序列表有n-2 的数据 arr[1] ~ arr[n-1]。排序开始...

    shengjk1
  • 关于Iterator和Iterable

    shengjk1
  • 排序算法总括-java版

    内部排序就是仅仅依赖于内存就可以进行的排序,比如有交换排序、插入排序、选择排序、归并排序、基数排序

    shengjk1
  • 谈谈fail-fast与fail-safe

    fail-fast的字面意思是“快速失败”。当我们在遍历集合元素的时候,经常会使用迭代器,但在迭代器遍历元素的过程中,如果集合的结构被改变的话,就会抛出异常,防...

    帅地
  • 实时音视频,小程序端WebRTC互通

    我们在 LiteAVSDK 的最新版本里面加入了对 WebRTC 的支持能力,并且已经跟随微信APP的 6.6.6 版本发布出来,此文档主要介绍如何使用原生的 ...

    用户5916837
  • 因果图在运维工作中的应用

    因果图在运维工作中的应用 摘要 我的系列文档 Netkiller Architect 手札 Netkiller Developer 手札 Netkill...

    netkiller old
  • 为什么阿里Java规约要求谨慎使用SimpleDateFormat

    在阿里Java开发规约中,有强制性的提到SimpleDateFormat 是线程不安全的类 ,在使用的时候应当注意线程安全问题,如下:

    Happyjava
  • Hibernate合并查询结果集为实体类

    用过mybatis的小伙伴可能都知道,我们可以查询两个表的部分字段合并为一个实体。然而用了Hibernate这么久了,居然还不知道也有此神器。

    小柒2012
  • DNS域名解析服务及其配置

    到 20 世纪 70 年代末,ARPAnet 是一个拥有几百台主机的很小很友好的网络。仅需要一个名为 HOSTS.TXT 的文件就能容纳所有需要了解的主机信息:...

    宜信技术学院
  • Hibernate合并查询结果集为实体类

    用过mybatis的小伙伴可能都知道,我们可以查询两个表的部分字段合并为一个实体。然而用了Hibernate这么久了,居然还不知道也有此神器。 ? hibern...

    小柒2012

扫码关注云+社区

领取腾讯云代金券