谢　婷（1.马鞍山市委党校，安徽 马鞍山243011；2马鞍山电视大学，安徽 马鞍山243011）

希尔排序算法设计思想研究

谢婷1，2
（1.马鞍山市委党校，安徽 马鞍山243011；2马鞍山电视大学，安徽 马鞍山243011）

根据对希尔排序算法原理的研究分析，指出希尔算法的执行时间是受文件大小、扫描次数等因素影响，其中影响最大的是增量序列的选取，通过实验证明，增量序列为N/3+1，N/9+1，N/27+1…，1时，程序排序效率比使用序列N/2，N/4，N/8，…，1要高。

希尔排序；算法；增量序列；时间复杂度

随着计算机信息技术的普及，算法也已成为计算机学科的重要研究对象。算法这一词汇是由数学家al-Khwarizmi的名字音译过来的，直到1936年图灵机这一现代计算机的基本模型出现后，算法的概念才算明确起来：算法就是按部就班地解决一个问题或完成一个目标的过程［1］。排序在算法中占有很重要的地位，排序算法在数据处理领域中是一种最常用的非数值算法，在计算机信息处理、数据库操作、数据分析等方面起着重要的作用。希尔排序算法是Donald.L. Shell于1959年提出的一种插入排序算法。希尔算法所占用的内存少，排序速度快，这就使得这种排序算法在记录较多时更具有使用价值。

一、希尔排序算法原理

希尔排序算法［2］：首先存在排列记录R1，R2，…RN；在完成排序以后，它们的关键码是有序的：K1＜= K2＜=…＜=KN。用一个辅助的增量序列ht，ht-1，…，h0来控制这个排序的过程，其中h0=1，t为程序的扫描次数｀；适当选择增量可以显著地减少排序时间，当t=1时，这个算法退化为直接插入排序法。

步骤1：［设置s循环］对s=t，t-1，…，0实施步骤2；……