-
题名缫丝排序算法
被引量:5
- 1
-
-
作者
杨帆
王箭
柳亚男
曹蕊
-
机构
南京航空航天大学计算机科学与技术学院
-
出处
《计算机学报》
EI
CSCD
北大核心
2012年第4期802-810,共9页
-
基金
国家"八六三"高技术研究发展计划项目基金(2009AA044601)资助~~
-
文摘
文中提出一种改进的排序算法,弥补了快速排序在大规模下堆栈低效及合并排序在小规模下优势不明显的问题.算法扩展了合并排序思想,从一种特殊的蚕茧缫丝工艺得到启发,使用2~6个滚轴分离待排序列中的有序片段,在滚轴始末端扩展新数据,从而达到在合并操作前增加有序子序列长度的目的.理论推导表明,缫丝排序中的基本操作数量较合并排序减少4.75 N,相当于将待排序列缩小至原有规模的1/4;效率测试实验表明,缫丝排序在各种规模下均能获得相比最快经典排序算法10%~15%的稳定优势,相比前人的改进排序算法具备相当的互补性,并能有效降低排序库函数自适应选择算法的实现复杂度.
-
关键词
缫丝排序
快速排序
自底向上合并排序
随机序列
有序片段
-
Keywords
ReelingSort
quicksort
bottomup mergesort
random sequence
ordered segments
-
分类号
TP309
[自动化与计算机技术—计算机系统结构]
-