希尔排序分析

摘要：

希尔排序的时间复杂度依赖增量序列,其详细分析至今未能解决。该文分析平均情况下的希尔排序的性质,从元素随机分布的角度入手,统计所有元素移动时跨越元素的个数平均值作为增量进行一轮排序,使元素尽可能快速的接近于最终位置,推导出一个理论上的公式。通过实验模拟,筛选出来一个性能较优的增量序列（3,2.8）,需要log^-1（2.8）log（2.8n/3）轮排序。大量的实验表明,平均时间性能优于已知最好的增量序列。

关键词：希尔排序、增量序列、支配概率

分类号：TP301(计算技术、计算机技术)

在线出版日期：2012-04-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：72-73