我要评论开始之前
假设最长字符串的长度是l，以l作为输入的长度， 然后假定所有的字符串都"补齐"到此长度，这个补齐只是逻辑上的，我们可以假想有一种"空字符"， 它小于任何其它字符，用此字符补齐所有长度不足的字符串。例如：最长的字符串长度为9，有一个字符串a长度为6， 那么当比较第7位字符的时候，我们让a[7]为"空字符"。
如果要包含所有的字符似乎并不容易，我们先定义一个字符集， 待排序字符串中的所有字符都包含在这个字符集里
//字符集 private string _mycharset = "0123456789qwertyuiopasdfghjklzxcvbnm";
再来一个生成随机字符串的方法(c#实现)：
private random _random = new random();
string[] getrandstrings(int size, int minlength, int maxlength)
{
string[] strs = new string[size];
int len = 0;
stringbuilder sb = new stringbuilder(maxlength);
for (int i = 0; i < strs.length; i++)
{
//先随机确定一个长度
len = _random.next(minlength, maxlength);
for (int j = 0; j < len; j++)
{
//随机选取一个字符
sb.append(_mycharset[_random.next(_mycharset.length)]);
}
strs[i] = sb.tostring();
sb.clear();
}
return strs;
}
这里按照字符的整数表示来确定桶的范围，再为"空字符"准备一个桶。 为了表示"空字符"这个特例，这里用default(char)，即'\0'表示它， 因为当调用string.elementatordefault(int)方法时，如果超出索引会返回'\0'。
初级版本(c#)
void stringradixsort(string[] strarray)
{
if (strarray == null
|| strarray.length == 0
|| strarray.contains(null))
{
return;
}
//获得字符串的最大长度
int maxlength = 0;
foreach (string s in strarray)
{
if (s.length > maxlength)
{
maxlength = s.length;
}
}
//确定字符的整数范围
int rangestart = _mycharset[0];
int rangeend = _mycharset[0];
foreach (char ch in _mycharset)
{
if (ch < rangestart)
rangestart = ch;
if (ch >= rangeend)
rangeend = ch + 1;
}
//也要为"空字符"分配一个桶，其索引为0
int bucketcount = rangeend - rangestart + 1;
linkedlist<string>[] buckets = new linkedlist<string>[bucketcount];
//初始化所有的桶
for (int i = 0; i < buckets.length; i++)
{
buckets[i] = new linkedlist<string>();
}
//从最后一个字符开始排序
int currentindex = maxlength - 1;
while (currentindex >= 0)
{
foreach (string thestring in strarray)
{
//如果超出索引，返回'\0'字符(default(char))
char ch = thestring.elementatordefault(currentindex);
if (ch == default(char))
{ //"空字符"的处理
buckets[0].addlast(thestring);
}
else
{ //将字符映射到桶
int index = ch - rangestart + 1;
buckets[index].addlast(thestring);
}
}
//从桶里依次取回字符串，完成一趟排序
int i = 0;
foreach (linkedlist<string> bucket in buckets)
{
while (bucket.count > 0)
{
strarray[i++] = bucket.first();
bucket.removefirst();
}
}
currentindex--;
}
}
稍作"改良"
用作确定字符的整数范围的代码略显蛋疼，而且根据字符集来看， 并不是区间内所有的整数对应的字符都可能出现，因此会有这样的情况： 我们给某些根本不会出现的字符分配了桶，这纯属浪费。 我们可以用一个字典(散列)来记录字符和它的桶之间的映射。于是有了下面的代码。
private dictionary<char, int> _charorderdict =
new dictionary<char, int>(_mycharset.length);
void buildcharorderdict()
{
char[] sortedcharset = _mycharset.toarray();
//使用默认的比较器排序
array.sort(sortedcharset);
//为"空字符"单独创建映射
_charorderdict.add(default(char), 0);
for (int i = 0; i < sortedcharset.length; i++)
{
// 保存的是字符及其对应的桶的索引
_charorderdict.add(sortedcharset[i], i + 1);
}
}
也可以不用默认的字符排序来作为映射，而完全自己定义字符之间的大小关系。 下面是调整后的代码：
void stringradixsort(string[] strarray)
{
if (strarray == null
|| strarray.length == 0
|| strarray.contains(null))
{
return;
}
//获得字符串的最大长度
int maxlength = 0;
foreach (string s in strarray)
{
if (s.length > maxlength)
{
maxlength = s.length;
}
}
//为每一个字符(包括空字符'\0')分配一个桶
//"空字符"索引应为0
int bucketcount = _mycharset.length + 1;
linkedlist<string>[] buckets = new linkedlist<string>[bucketcount];
//初始化所有的桶
for (int i = 0; i < buckets.length; i++)
{
buckets[i] = new linkedlist<string>();
}
//从最后一个字符开始排序
int currentindex = maxlength - 1;
while (currentindex >= 0)
{
foreach (string thestring in strarray)
{
//如果超出索引，返回'\0'字符(default(char))
char ch = thestring.elementatordefault(currentindex);
//根据字符顺序的定义查询字符
int index = _charorderdict[ch];
buckets[index].addlast(thestring);
}
//从桶里依次取回字符串，完成一趟排序
int i = 0;
foreach (linkedlist<string> bucket in buckets)
{
while (bucket.count > 0)
{
strarray[i++] = bucket.first();
bucket.removefirst();
}
}
currentindex--;
}
}
now, it works! 如果采用的快速排序来做， 其时间复杂度为o(n∗logn)o(n∗logn)。表面上看，基数排序更好，不过严格来说， 基数排序的时间复杂度应该是o(k∗n)o(k∗n)，其中k和字符串长度正相关。 此时两种算法的比较可以通过比较k和lognlogn的比较结果近似得出。 如果字符串的长度很长，即k很大，而输入规模n不大的时候， 就会有k>lognlogn，此时快速排序反而更有优势。反之，则基数排序可能更优。
最后...
杯具的是，当我扩大字符集，将键盘上所有字符都加进去后， 发现基数排序的结果和array.sort(string[]方法的排序结果并不一样。 仔细观察资源管理器对文件名的排序，才发现其字符串排序的规则要复杂的多，并非简单的比较字符。 查询相关资料后发现，字符串的排序甚至还要考虑区域文化的影响，即使都是拉丁字母， 不同地区的排序规则都可能不一样，因此， 使用基数排序实现的字符串排序算法好像并无多大实用价值<t-t>。
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论