希尔排序分析

• 作者: 庞伟
• 来源期刊: 科协论坛：下半月
• 学科: 工学
• 关键词: 希尔排序 增量序列 支配概率
• 年，卷（期）: 2011,（7）
• 所属期刊栏目: 科研探索与知识创新
• 页码范围: 72-73
• 分类号: TP301
• 字数: 2681字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-3973.2011.07.044

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	庞伟	中国矿业大学计算机系	2	1	1.0	1.0