一.排序方法
- 先取一个小于n的整数increment作为第一个增量,把文件的全部记录分成increment个组。所有距离为increment的倍数的记录放在同一个组中。先在各组内进行直接插人排序。
- 取第二个增量increment(小于1中的increment)重复上述的分组和排序,直至所取的增量increment=1,即所有记录放在同一组中进行直接插入排序为止。
- 希尔排序实质上是一种分组插入方法。
二.动画演示
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/shell.htm
三.Java代码
- public static int[] shellSort(int[] data) {
- int increment = data.length; // 区间为increment
- int temp = 0;
- while (true) {
- increment = increment / 2; //开始每两个为一组,
- // 分成了几组,一组一组处理
- for (int x = 0; x < increment; x++) { //每次比较要处理多少组
- // 下面就是直接插入排序,只是区间由1变成了increment
- for (int i = x + increment; i < data.length; i += increment) { //保证每次迭代所有数据都会比较,从这里也可以看出每组数据相隔 increment,细看
- if (data[i - increment] > data[i]) {
- temp = data[i];
- int j = i - increment;
- for (; j >= 0 && data[j] > temp; j -= increment) {
- data[j + increment] = data[j];
- }
- data[j + increment] = temp;
- }
- }
- }
- if (increment == 1) {
- break;
- }
- }
- return data;
- }
四. 时间复杂度和稳定性
- 希尔排序的时间复杂度到现在都还没有定论是多少,原因是因为希尔排序需要大量的数学知识做支撑。如果面试被问到,就说法复杂度介于O (n log2n )-O( ns ) 1<s<2。 希尔排序时间复杂度最坏情况下为O(n2 ),其平均时间复杂度与每次选择的增量密切相关,但要优于直接插入排序。
- 希尔排序是不稳定的。
相关推荐
51单片机控制的循迹避障小车,支持红外遥控,可以实现前进后退左右和循迹切换
智能小车的相关功能例程,并且有程序的注释,
ZY3-01星SC产品命名规范20160217.pdf
该套设备采用ZY6400-23.5/45型液压支架,最大采高达4.5 m。由于十二矿井下主要巷道断面较小,支架必须解体入井安装,回采结束后支架回撤又面临一个新课题。针对这个难题,十二矿改革回收工艺,采取相应的安全措施,顺利地...
ZY-Player-Setup-2.6.4.exe
RF-SJ-ZY-04-F03 结构专业图纸审查标准及要点.zip
ZY-TP21便捷式打印机驱动是一款嵌入式微型打印机,这款打印机体积小,重量轻,噪音低,易集成,操作简单,可靠性强,这里介绍的正是针对这款打印机的驱动,ZY-TP21便捷式打印机驱动,有需要的朋友们快来下载吧。...
循迹小车的单片机程序。仅供参考大家互相学习,共同进步本次上传日志本次上传日志本次上传日志本次上传日志要求上传您自己觉得好的资料本次上传日志
不用换找资源,本身自带资源搜索的播放器
RF-SJ-ZY-04-F03 结构专业图纸审查标准及要点(1).zip
ZY-Player-Setup-2.6.1.exe
RF-GC-ZY-04-F03 管道打压验收标准.zip
zy-player PC端
RF-GC-ZY-04-F01 房屋验收记录单.zip
程序设计语言ZY1906-大作业.7z
ZY-Player清醒脱俗的一款播放器,无广告,速度快。
ZY5600-16-34型液压支架掩护梁有限元分析及其优化设计,蒲志新,邓全刚,以ZY5600-16-34型液压支架为研究对象,利用Pro/E软件对其液压支架进行三维建模,然后利用ANSYS软件对液压支架的强度进行有限元分析,并�
RF-SJ-ZY-04-F08 采暖通风设计图纸审查标准及要点(1).zip