基于数组的桶排序算法.pdf

计算机研究与发展 lSSN 1000-1239!CN 11-1777!TP Journal of Com uter Research and develo ment 44（）： ， p p 2 341347 2007 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 基于数组的桶排序算法 杨 磊 宋 涛 （清华大学计算机科学与技术系 北京 100084 ） （an lei96#mails.tsin hua .edu .cn ） y g g The arra -based bucket Sort al orithm y g Yang Lei and Song Tao （ ， ， ） De artment o Com uter science and technolo tsin hua unioersit Bei in 100084 P f P gy g y j g abstract Classical bucket sort al orithm im lements buckets as d namic lists . lt sorts uniform data g p y 2 （ ） （ ） eff icientl Within 0 N time but de rades to the ineff icient 0 N insertion sort When handlin y g g extremel -nonuniform data . B anal Zin countin sort With extra data，a method is presented to y y y g g im lement the buckets as se uential arra s . The eff icienc is im roved directl b avoidin the com lex p C y y p y y g p o erations of d namic memor allocation . f urthermore， （ ） p y y 0 N lo N al orithms like uicksort ma be g g