缫丝排序算法

• 作者: 曹蕊 杨帆 柳亚男 王箭
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 缫丝排序 快速排序 自底向上合并排序 随机序列 有序片段
• 年，卷（期）: 2012,（4）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 802-810
• 分类号: TP309
• 字数: 6471字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2012.00802

摘要

文中提出一种改进的排序算法,弥补了快速排序在大规模下堆栈低效及合并排序在小规模下优势不明显的问题.算法扩展了合并排序思想,从一种特殊的蚕茧缫丝工艺得到启发,使用2～6个滚轴分离待排序列中的有序片段,在滚轴始末端扩展新数据,从而达到在合并操作前增加有序子序列长度的目的.理论推导表明,缫丝排序中的基本操作数量较合并排序减少4.75N,相当于将待排序列缩小至原有规模的1/4;效率测试实验表明,缫丝排序在各种规模下均能获得相比最快经典排序算法10％～15％的稳定优势,相比前人的改进排序算法具备相当的互补性,并能有效降低排序库函数自适应选择算法的实现复杂度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曹蕊	南京航空航天大学计算机科学与技术学院	2	8	2.0	2.0
2	杨帆	南京航空航天大学计算机科学与技术学院	20	38	3.0	4.0
3	王箭	南京航空航天大学计算机科学与技术学院	49	315	9.0	15.0
4	柳亚男	南京航空航天大学计算机科学与技术学院	4	21	3.0	4.0