计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2012年
4期
802-810
,共9页
杨帆%王箭%柳亚男%曹蕊
楊帆%王箭%柳亞男%曹蕊
양범%왕전%류아남%조예
缫丝排序%快速排序%自底向上合并排序%随机序列%有序片段
繅絲排序%快速排序%自底嚮上閤併排序%隨機序列%有序片段
소사배서%쾌속배서%자저향상합병배서%수궤서렬%유서편단
文中提出一种改进的排序算法,弥补了快速排序在大规模下堆栈低效及合并排序在小规模下优势不明显的问题.算法扩展了合并排序思想,从一种特殊的蚕茧缫丝工艺得到启发,使用2～6个滚轴分离待排序列中的有序片段,在滚轴始末端扩展新数据,从而达到在合并操作前增加有序子序列长度的目的.理论推导表明,缫丝排序中的基本操作数量较合并排序减少4.75N,相当于将待排序列缩小至原有规模的1/4;效率测试实验表明,缫丝排序在各种规模下均能获得相比最快经典排序算法10％～15％的稳定优势,相比前人的改进排序算法具备相当的互补性,并能有效降低排序库函数自适应选择算法的实现复杂度.
文中提齣一種改進的排序算法,瀰補瞭快速排序在大規模下堆棧低效及閤併排序在小規模下優勢不明顯的問題.算法擴展瞭閤併排序思想,從一種特殊的蠶繭繅絲工藝得到啟髮,使用2～6箇滾軸分離待排序列中的有序片段,在滾軸始末耑擴展新數據,從而達到在閤併操作前增加有序子序列長度的目的.理論推導錶明,繅絲排序中的基本操作數量較閤併排序減少4.75N,相噹于將待排序列縮小至原有規模的1/4;效率測試實驗錶明,繅絲排序在各種規模下均能穫得相比最快經典排序算法10％～15％的穩定優勢,相比前人的改進排序算法具備相噹的互補性,併能有效降低排序庫函數自適應選擇算法的實現複雜度.
문중제출일충개진적배서산법,미보료쾌속배서재대규모하퇴잔저효급합병배서재소규모하우세불명현적문제.산법확전료합병배서사상,종일충특수적잠충소사공예득도계발,사용2～6개곤축분리대배서렬중적유서편단,재곤축시말단확전신수거,종이체도재합병조작전증가유서자서렬장도적목적.이론추도표명,소사배서중적기본조작수량교합병배서감소4.75N,상당우장대배서렬축소지원유규모적1/4;효솔측시실험표명,소사배서재각충규모하균능획득상비최쾌경전배서산법10％～15％적은정우세,상비전인적개진배서산법구비상당적호보성,병능유효강저배서고함수자괄응선택산법적실현복잡도.
