应用信息熵原理研究排序算法的效率

• 作者: 齐国清
• 来源期刊: 大连海事大学学报
• 学科: 工学
• 关键词: 数据结构 排序 信息熵 算法效率
• 年，卷（期）: 2002,（1）
• 页码范围: 85-88
• 页数: 4页
• 分类号: TP311.12
• 字数: 3229字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-7736.2002.01.023

摘要

应用信息熵的概念表示序列的无序程度并分析基于关键字间的比较的排序算法的效率.首先讨论了序列的信息熵的定义,证明了序列的信息熵即为基于直接比较的排序方法所需要的比较次数的理论下限.然后利用信息熵原理分析了插入排序和归并排序的效率,指出当序列长度大于4时,任何直接插入排序的比较次数大于理论下界.最后探讨了利用熵原理寻找比较次数最少的排序方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	齐国清	大连海事大学信息工程学院	27	1072	15.0	27.0