字符串基数排序

　　对字符串使用基数排序，以前，我一直觉得：因为字符串的长度不一，无法使用基数排序。前两天因为有需要，忽然想通了！即便长短不一，也可以使用链式基数排序！

　　首先，将字符串长度当作最低有效位，因为基数排序是从最低有效位开始排的，就先用分配-收集算法对长度做一趟。对字符串中的具体某一位字符进行排序相比，算法是一样的，只是写法稍有不同。要将排序结果的lenRadix指针保存起来，后面要用。

　　接下来，从lenRadix中取字符串最长的那个sublist，对该sublist排序，然后将这一趟的结果first保存起来，连接到长度次短的那个sublist之后，然后对这两个链接起来的列表进行一趟分配-收集。如此，直到最高有效位。

　　所有的工作就做完了，根据此算法，对所有待排序字符串中的每个字符，均需要一次且仅一次访问！另外，还需要O((radix+1)*max_str_len)的时间复杂度用于扫描链接表，(radix+1)是因为还有一个strlen链接表。所以，总的时间复杂度是O(n+(radix+1)*max_str_len)，其中N是所有字符串的总字符数。

　　在排序过程中，可以插入一个codetab，来实现不同的排序准则（例如忽略大小写），如果提供了wchar_t codetab，就按 wchar_t 排序，如果wchar_t codetab 非 NULL，就按转换了的 wchar_t 排序。

　　如果对unicode排序，最好指定一个codetab，把radix变小，不然的话，时间复杂度就太大了！

　　经过测试，在大约20000~30000个字符串的情况下，比std::sort快5~7倍。数据规模再增大，至5,000,000个字符串时，比std::sort大概快1.8~2.5倍！

 

代码：

http://code.google.com/p/febird/source/browse/trunk/febird/src/febird/radix_sort.cpp

http://code.google.com/p/febird/source/browse/trunk/febird/src/febird/radix_sort.h

 

测试(bench mark)代码：

http://code.google.com/p/febird/source/browse/trunk/febird/codelite/RadixSort/main.cpp