基于PAR的排序算法自动生成研究

• 作者: 石海鹤 薛锦云
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 排序算法 自动生成 领域特定语言 形式化模型 PAR方法
• 年，卷（期）: 2012,（9）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 2248-2260
• 页数: 13页
• 分类号: TP301
• 字数: 10721字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04164

摘要

排序是计算机学科中的一类特殊问题,其算法设计策略的灵活性使得求解算法更具多样性.基于形式化方法PAR(partition-and-recur),研究了排序算法的自动生成问题.刻画了排序问题的代数性质,形式化构建了排序算法领域的泛型类型构件和算法构件,建立了排序领域特定语言和算法生成形式化模型,以参数替换的方式自动生成了一组排序算法,包括快速排序、堆排序、Shell排序等典型的已知算法以及增量选择排序等若干未见于现有文献的算法,并在程序生成系统中予以了实现.通过上层框架研究和底层构件支持,显著提高了特定领域算法的开发效率和可靠性.