什么是希尔排序?
希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。其基本思想是:
先将整个待排序元素序列分割成若干子系列(由相隔某个增量的元素组成)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序时,再对全体匀速进行一次直接插入排序。
希尔排序过程详解
下面介绍使用扑克牌来演示希尔排序算法的详细过程。
准备扑克牌一副,红蓝色棋子各一枚,为便于演示,取牌面为1、5、6、7、9的5张纸牌进行排序操作。将5张牌打乱顺序,假定5张牌从左到右依次为6、7、9、1、5。对于5张纸牌,经过3轮排序即可完成。
第一轮排序:先计算间隔,用5除以2再四舍五入,gap = 5 / 2 = 3,以3为间隔放置两枚棋子,将红色棋子放在第1张纸牌上方,将蓝色棋子放在第4张纸牌上方。接着比较两张纸牌,纸牌1小于纸牌6,将两者交换位置。之后将两枚棋子分别向右移动一步,纸牌5小于纸牌7,将两者交换位置,到此第一轮排序结束,如图:
第二轮排序:缩小间隔,gap = gap / 2,即 3 / 2 = 1.5,四舍五入为2,以2为间隔放置两枚棋子,将红色棋子放在第1张纸牌上方,将蓝色棋子放在第3张牌上方。接着比较两张纸牌大小,纸牌1小于纸牌9,不用交换。再将两枚棋子分别右移一步,纸牌6大于纸牌5,不用交换。继续右移两枚棋子,纸牌7小于纸牌9,将两者进行位置交换,到此,结束第二轮排序,如图“
第三轮排序:继续缩小间隔,gap = 2 / 2 = 1,以1为间隔放置两枚棋子,将红色棋子放在第1张牌上方,蓝色棋子放在第2张牌上方,接着比较两处的纸牌,纸牌1小于纸牌5,不用交换。向右移动两枚棋子,进行比较,纸牌5小于纸牌7,无需交换。再分别将两枚棋子向右移动一步,纸牌6小于纸牌7,两者交换位置。继续右移棋子,纸牌7小于纸牌9,不用交换,至此第三轮排序结束,如图:
当间隔为1的排序过程结束后,5张纸牌已经按照从小到大的顺序排列完毕。
编程思路
依然遵循IPO设计原则,输入一个无序的列表,经过排序处理,再输出已排序的列表。重点是排序处理,不变的仍然是交换元素操作,所以还是要先定义好交换元素的自制积木,然后再定义一个自制积木,结合双重循环来完成排序。
程序实现
1. 建立“交换元素”自制积木
创建自制积木,将其命名为“交换元素”,代码如下:
2. 建立“希尔排序”自制积木
创建自制积木,并命名为“希尔排序”,具体的代码如下:
3. 完成排序
接下来,我们就可以准备好列表数据,使用“希尔排序”自制积木完成排序,具体的代码如下:
作品效果
Scratch希尔排序的执行效果如图所示:
暂无评论内容