算法回顾系列第五篇:希尔排序
---------------------------------------
希尔排序(缩小增量排序)
基本原理:
该方法实质上是一种分组插入排序方法,属于直接插入排序的改进算法。
比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。
算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d。
对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。
当增量减到1时,整个要排序的数被分成一组,排序完成。
(一般初次取序列一半为增量,然后每次减半,直到增量为1。)
程序实现:
public void sort(int[] data) {
//初次取序列长度一半为增量(相隔距离),以后每次减半,直到增量为1.
for(int i=data.length/2;i>2;i/=2){//i为增量,若大于2,则每次递减一半.
//每次增量缩小后都需要从头进行一次排序.
for(int j=0;j<i;j++){
insertSort(data,j,i);//起始为0,增量不为1的插入排序.
System.out.println("after insert sort:"+Arrays.toString(data));
}
System.out.println("sort:"+Arrays.toString(data));
}
insertSort(data,0,1);//起始为0,增量是1的直接插入排序.
System.out.println("after final sort:"+Arrays.toString(data));
}
/**
* 与直接插入排序实现类似,只不过增量不一定为1(不是相邻元素交换位置).
* @param data 待排序数组
* @param start 起始位置
* @param inc 增量
*/
private void insertSort(int[] data, int start, int inc){
int temp;
for(int i=start+inc;i<data.length;i+=inc){
for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
temp = data[j];
data[j] = data[j-inc];
data[j-inc] = temp;
//System.out.println("after swap:"+Arrays.toString(data));
}
}
}
public static void main(String[] args){
int[] data = new int[]{12,11,10,9,8,7,6,5,4,3,2,1};
new ShellSort().sort(data);
System.out.println(Arrays.toString(data));
}
上面程序中:
一共12个元素,增量分别为6,3,1.
第一次以6为增量分组,每组元素(相差距离为6)进行直接插入排序。
第二次以3为增量分组,每组元素(相差距离为3)进行直接插入排序。
最后以1为增量分组(即全部元素),进行一次直接插入排序。
性能分析:
平均时间复杂度 O(nlogn),最差时间复杂度O(n^2)。
空间复杂度:1。
稳定性:不稳定。
分享到:
相关推荐
- **实现细节**:希尔排序是插入排序的一种更高效的变体,通过引入增量序列来分组元素,逐步缩小增量,直至最终增量为1时完成排序。 ##### 5. 快速排序 - **复杂度**:平均时间复杂度为O(n log n),最坏情况下为O(n...
Shell排序,由Hibbard于1959年提出,是一种基于插入排序的算法,通过设置一个间隔序列(也称为希尔增量)来改进了传统插入排序的效率。它的工作原理是将待排序的数据分成若干个子序列,每个子序列使用插入排序进行...
python学习资源
jfinal-undertow 用于开发、部署由 jfinal 开发的 web 项目
基于Andorid的音乐播放器项目设计(国外开源)实现源码,主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。
python学习资源
python学习资源
python学习一些项目和资源
【毕业设计】java-springboot+vue家具销售平台实现源码(完整前后端+mysql+说明文档+LunW).zip
HTML+CSS+JavaScarip开发的前端网页源代码
python学习资源
【毕业设计】java-springboot-vue健身房信息管理系统源码(完整前后端+mysql+说明文档+LunW).zip
成绩管理系统C/Go。大学生期末小作业,指针实现,C语言版本(ANSI C)和Go语言版本
1_基于大数据的智能菜品个性化推荐与点餐系统的设计与实现.docx
【毕业设计】java-springboot-vue交流互动平台实现源码(完整前后端+mysql+说明文档+LunW).zip
内容概要:本文主要探讨了在高并发情况下如何设计并优化火车票秒杀系统,确保系统的高性能与稳定性。通过对比分析三种库存管理模式(下单减库存、支付减库存、预扣库存),强调了预扣库存结合本地缓存及远程Redis统一库存的优势,同时介绍了如何利用Nginx的加权轮询策略、MQ消息队列异步处理等方式降低系统压力,保障交易完整性和数据一致性,防止超卖现象。 适用人群:具有一定互联网应用开发经验的研发人员和技术管理人员。 使用场景及目标:适用于电商、票务等行业需要处理大量瞬时并发请求的业务场景。其目标在于通过合理的架构规划,实现在高峰期保持平台的稳定运行,保证用户体验的同时最大化销售额。 其他说明:文中提及的技术细节如Epoll I/O多路复用模型以及分布式系统中的容错措施等内容,对于深入理解大规模并发系统的构建有着重要指导意义。
基于 OpenCV 和 PyTorch 的深度车牌识别
【毕业设计-java】springboot-vue教学资料管理系统实现源码(完整前后端+mysql+说明文档+LunW).zip
此数据集包含有关出租车行程的详细信息,包括乘客人数、行程距离、付款类型、车费金额和行程时长。它可用于各种数据分析和机器学习应用程序,例如票价预测和乘车模式分析。
把代码放到Word中,通过开发工具——Visual Basic——插入模块,粘贴在里在,把在硅基流动中申请的API放到VBA代码中。在Word中,选择一个问题,运行这个DeepSeekV3的宏就可以实现在线问答