java 数据结构 希尔排序 解释代码
本人现在在看java数据结构和算法(第二版),对这段代码不懂,希望高手能帮忙解释下
部分代码如下:
public void shellSort{
int inner, outer;
long temp;
int h = 1;
while(h <= nElems/3)
h = h*3 + 1;
while(h > 0){
for(outer = h; outer < nElems; outer++){
temp = theArray[outer];
inner = outer;
while(inner > h - 1 && theArray[inner - h] >= temp){
theArray[inner] = theArray[inner - h];
inner -= h;
}
theArray[inner] = temp;
}
h = (h - 1)/3;
}
}
首先先用网上查来的数据解释下希尔排序:
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
然后说下希尔排序的实质:该方法实质上是一种分组插入方法。
再说下该排序好处:希尔排序的时间性能优于直接插入排序的原因:
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
因此,希尔排序在效率上较直接插人排序有较大的改进。
好了,开始解释你的代码。
首先 该代码是以h的值为分组的。h = h*3 + 1; 和h = (h - 1)/3; 可以使h的值产生不同的值,就可以使数组分成几组。然后就是在每个组里进行插入排序方法。随着h值的越来越小,排序也越来越细致。当h=1时,就相当于在进行一次彻底插入排序。只不过这是整个队列已经接近排序后的数组,所以要比直接用插入排序速度快。
这就是该代码的精髓分析了。
分享到:
相关推荐
Java数据结构的作业,写出直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、归并排序的算法,并用动态界面展示出来。
总结的不错,值得一看 ...插入排序(直接插入排序、折半插入排序、希尔排序); * 2.交换排序(冒泡泡排序、快速排序); * 3.选择排序(直接选择排序、堆排序); * 4.归并排序; * 5.基数排序。
JAVA数据结构与算法课程第05课双端链表和双向链表.mp4JAVA数据结构与算法课程第06课递归的应用.mp4JAVA数据结构与算法课程第07课递归的高级应用.mp4JAVA数据结构与算法课程第08课希尔排序.mp4JAVA数据结构与算法课程...
Java语言编写的数据结构-排序。包括冒泡排序、选择排序、插入排序、希尔排序、快排、堆排序。
主要为大家详细介绍了java数据结构之希尔排序的相关代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...
各个排序算法的java实现 包括 插入排序(直接插入和希尔排序) 交换排序(起泡排序和快速排序) 选择排序(简单选择和堆排序) 归并排序
适用人群:本人文档是通过Java语言来编写数据结构中排序的算法,所以要具备一定Java编程基础。以及想要复习或者自学数据结构的小伙伴。 能学到什么:1.六个基础排序算法,分别是冒泡排序,选择排序,插入排序,希尔...
用java实现了10种基础排序,其内容包括: 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.桶排序 9.基数排序 10.计数排序 如有疑问请私信我
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
希尔排序的原理详见Java之希尔排序: https://blog.csdn.net/qq_43437122/article/details/105890206 代码如下: # author atguigu def shell_sort(arr_list): ''' 交换法,用希尔排序方法对列表进行排序 参数: ...
主要介绍了java数据结构与算法之希尔排序,结合实例形式分析了希尔排序的概念、原理、实现方法与相关注意事项,需要的朋友可以参考下
Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示一切? 小...
(1)数据结构与算法概念解析 (2)数据结构之数组 (3)数据结构之栈 (4)数据结构之队列 (5)数据结构之链表 (6)数据结构之二叉树 (7)数据结构之霍夫曼树 (8)数据结构之红黑树(一)——基础分析 ...
Java数据结构和算法中文第二版(1) Java数据结构和算法中文第二版(2) 【内容简介】 本书可帮助读者: 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择...
第08讲 - 希尔排序 第09讲 - 快速排序 第10讲 - 二叉树的基本概念 第11讲 - 二叉树的基本操作 第12讲 - 遍历二叉树 第13讲 - 删除二叉树节点 第14讲 - 红黑树 第15讲 - 哈希表 第16讲 - 开放地址法 第17讲...
通过实验,帮助学生由浅入深地掌握各种简单排序和高级排序的基本思想,让他们比较其性能,也让他们更好地理解希尔排序和快速排序的方法。 1.任意输入一个数组并利用简单选择排序算法对此数组的元素按从大到小的顺序...
主要介绍了数据结构基本算法希尔排序的相关资料,需要的朋友可以参考下
本项目主要使用Java实现各种经典常用数据结构及其算法,包括但不仅限于链表、栈,队列,树,图等经典数据结构。 八大排序算法及其实现,具体包括直接插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序...
Java开发课程设计基于swing做的数据结构演示系统源代码。介绍 排序算法 包括直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序,可以实现十个数的排序演示,有追踪数据变化的功能。 二叉树遍历 该模块实现...