0%
这是一片思考的空间 -- arthinking
Spring 重构&代码整洁之道 软件设计 JVM 并发编程 数据结构与算法 分布式 存储 网络 微服务 设计模式
Java技术栈 - 涉及Java技术体系

数据结构笔记 - 排序算法 希尔排序算法

希尔排序:

将相距一个增量单位的元素集组成一个子集,然后通过以子集为单位对数据进行比较,最后得到子集间的数据是有序的,但是子集内德数据还未排序。这样继续缩小增量循环比较进行互换位置处理,直到增量变为1时为最后一次循环比较。

希尔排序算法突破了O(n^2)的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>

#define MAXSIZE 100 /* 待排序数组的大小 */

typedef struct
{
int r[MAXSIZE+1]; /* 待排序数组r,r[0]为哨兵或临时变量 */
int length; /* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 希尔排序算法 */
void ShellSort(SortList *L)
{
int i,j,k=0;
/* 初始化增量为待排序数组的长度 */
int increment=L->length;
do
{
/* 设置增量 */
increment=increment/3+1;
for(i=increment+1; i<=L->length; i++)
{
/* 比较r[i]与r[i-increment]的值,即相差一个增量的元素相互比较 */
if (L->r[i]<L->r[i-increment])
{
/* r[i]记录暂存到r[0]中 */
L->r[0]=L->r[i];
for(j=i-increment; j>0 && L->r[0]<L->r[j]; j-=increment) {
L->r[j+increment]=L->r[j];
}
L->r[j+increment]=L->r[0]; /* 插入到相应位置 */
}
}
}
while(increment>1);
}

时间复杂度分析:

由于希尔排序是基于增量把数组分成几个子集的,从而实现了跳跃式的移动,提高了排序效率。

而增量大小的选择直接影响了排序的效率。研究表明当增量序列为increment[n]=2^(t-k+1) (0<=k<=t<=log2(n+1))时,排序的效率比较高,时间复杂度为O(n^(3/2))。

希尔排序是一种不稳定的排序算法。

欢迎关注我的其它发布渠道

订阅IT宅
内功修炼
Java技术栈
Java架构杂谈是IT宅精品文章公众号,欢迎订阅:
📄 网络基础知识:两万字长文50+张趣图带你领悟网络编程的内功心法 📄 HTTP发展史:三万长文50+趣图带你领悟web编程的内功心法 📄 HTTP/1.1:可扩展,可靠性,请求应答,无状态,明文传输 📄 HTTP/1.1报文详解:Method,URI,URL,消息头,消息体,状态行 📄 HTTP常用请求头大揭秘 📄 HTTPS:网络安全攻坚战 📄 HTTP/2:网络安全传输的快车道 📄 HTTP/3:让传输效率再一次起飞 📄 高性能网络编程:图解Socket核心内幕以及五大IO模型 📄 高性能网络编程:三分钟短文快速了解信号驱动式IO 📄 高性能网络编程:彻底弄懂IO复用 - IO处理杀手锏,带您深入了解select,poll,epoll 📄 高性能网络编程:异步IO:新时代的IO处理利器 📄 高性能网络编程:网络编程范式 - 高性能服务器就这么回事 📄 高性能网络编程:性能追击 - 万字长文30+图揭秘8大主流服务器程序线程模型
📄 Java内存模型:如果有人给你撕逼Java内存模型,就把这些问题甩给他 📄 一文带你彻底理解同步和锁的本质(干货) 📄 AQS与并发包中锁的通用实现 📄 ReentrantLock介绍与使用 📄 ReentrantReadWriteLock介绍与使用 📄 ReentrantLock的Condition原理解析 📄 如何优雅的中断线程 📄 如何优雅的挂起线程 📄 图解几个好玩的并发辅助工具类 📄 图解BlockingQueue阻塞队列
📄 消息队列那么多,为什么建议深入了解下RabbitMQ? 📄 高并发异步解耦利器:RocketMQ究竟强在哪里? 📄 Kafka必知必会18问:30+图带您看透Kafka
📄 洞悉MySQL底层架构:游走在缓冲与磁盘之间 📄 SQL运行内幕:从执行原理看调优的本质 📄 洞悉Redis技术内幕:缓存,数据结构,并发,集群与算法