|
|||||
|
|
| 一种改进的中文字符串排序方法 | |
| 引用本文： | 张海军,丁溪源,朱朝勇.一种改进的中文字符串排序方法[J].计算机工程与应用,2010,46(19):129-131. |
| 作者姓名： | 张海军 丁溪源 朱朝勇 |
| 作者单位： | 1. 新疆师范大学,计算机科学与技术系,乌鲁木齐,830054;中国科学院,计算机语言信息工程研究中心,北京,100097;中国科学技术大学,计算机科学与技术学院,合肥,230027 2. 中国科学院,计算机语言信息工程研究中心,北京,100097 3. 中国科学院,计算机语言信息工程研究中心,北京,100097;中国科学技术大学,计算机科学与技术学院,合肥,230027 |
| 基金项目： | 国家自然科学基金，国家高技术研究发展计划(863) |
| 摘 要： | 对中文字符串排序，最快算法的时间复杂度是O（nlgn）。基数排序算法是目前最快的排序方法之一，时间复杂度是O（dn），但其一般适用于相同长度的整型数据排序。提出了一种快速的变换方法，将字符串转换为与之等长的整型数组，使用基数排序算法对代表字串的整型数组排序，用以实现对字符串的快速排序。实验表明，提出的算法能快速地进行中文字符串排序，比快速排序算法具有更好的性能，且排序时间与数据规模之间是线性关系，算法的时间复杂度为O（dn）。 |
| 关 键 词： | 中文字符串 基数排序 散列表 时间复杂度 |
| 收稿时间： | 2009-12-28 |
| 修稿时间： | 2010-3-22 |
Improved sort method for Chinese strings |
|
| ZHANG Hai-jun,DING Xi-yuan,ZHU Chao-yong.Improved sort method for Chinese strings[J].Computer Engineering and Applications,2010,46(19):129-131. | |
| Authors: | ZHANG Hai-jun DING Xi-yuan ZHU Chao-yong |
| Affiliation: | 2,3 1.Department of Computer Science and Technology,Xinjiang Normal University,Urumqi 830054,China 2.Research Center of Computer ＆ Language Information Engineering,Chinese Academy of Sciences,Beijing 100097,China 3.School of Computer Science and Technology,University of Science and Technology of China,Hefei 230027,China |
| Abstract: | 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）. |
| Keywords: | Chinese string radix sort hash table time complexity |
| 本文献已被 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 | |
| 点击此处可从《计算机工程与应用》下载全文 | |
