一种改进的中文字符串排序方法  

Improved sort method for Chinese strings

作　　者：张海军[1,2,3] 丁溪源[2] 朱朝勇[2,3] 

机构地区：[1]新疆师范大学计算机科学与技术系,乌鲁木齐830054 [2]中国科学院计算机语言信息工程研究中心,北京100097 [3]中国科学技术大学计算机科学与技术学院,合肥230027

出　　处：《计算机工程与应用》2010年第19期129-131,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60672149);国家高技术研究发展计划(863)(No.2006AA010109)~~

摘　　要：对中文字符串排序,最快算法的时间复杂度是O(nlgn)。基数排序算法是目前最快的排序方法之一,时间复杂度是O(dn),但其一般适用于相同长度的整型数据排序。提出了一种快速的变换方法,将字符串转换为与之等长的整型数组,使用基数排序算法对代表字串的整型数组排序,用以实现对字符串的快速排序。实验表明,提出的算法能快速地进行中文字符串排序,比快速排序算法具有更好的性能,且排序时间与数据规模之间是线性关系,算法的时间复杂度为O(dn)。At present,the time complexity of the fastest sort algorithm for Chinese strings is O（nlgn）.Radix sort algorithm, whose time complexity is O（dn）,is one of the most efficient sort methods,but it is fit for integer data with identical digits.This paper puts forward a fast transform method used to convert strings to an integer arrays with identical length.The integer arrays representing strings are sorted by radix sort algorithm to achieve rapid sort for Chinese strings.Experiments show that the improved algorithm can quickly sort Chinese strings and its performance is better than that of quick sort algorithm.The relationship between sort time and data size is linear and the time complexity of the algorithm is O（dn）.

关 键 词：中文字符串 基数排序 散列表 时间复杂度 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]