Csharp/C#教程：C#中使用基数排序算法对字符串进行排序的示例分享

开始之前

假设最长字符串的长度是L，以L作为输入的长度，然后假定所有的字符串都”补齐”到此长度，这个补齐只是逻辑上的，我们可以假想有一种”空字符”，它小于任何其它字符，用此字符补齐所有长度不足的字符串。例如：最长的字符串长度为9，有一个字符串A长度为6，那么当比较第7位字符的时候，我们让A[7]为”空字符”。

如果要包含所有的字符似乎并不容易，我们先定义一个字符集，待排序字符串中的所有字符都包含在这个字符集里

//字符集 privatestring_myCharSet="0123456789qwertyuiopasdfghjklzxcvbnm";

再来一个生成随机字符串的方法(C#实现)：

privateRandom_random=newRandom(); string[]GetRandStrings(intsize,intminLength,intmaxLength) { string[]strs=newstring[size]; intlen=0; StringBuildersb=newStringBuilder(maxLength); for(inti=0;i<strs.Length;i++) { //先随机确定一个长度 len=_random.Next(minLength,maxLength); for(intj=0;j<len;j++) { //随机选取一个字符 sb.Append(_myCharSet[_random.Next(_myCharSet.Length)]); } strs[i]=sb.ToString(); sb.Clear(); } returnstrs; }

这里按照字符的整数表示来确定桶的范围，再为”空字符”准备一个桶。为了表示”空字符”这个特例，这里用default(char)，即’’表示它，因为当调用string.ElementAtOrDefault(int)方法时，如果超出索引会返回’’。

初级版本(C#)

voidStringRadixSort(string[]strArray) { if(strArray==null ||strArray.Length==0 ||strArray.Contains(null)) { return; } //获得字符串的最大长度 intmaxLength=0; foreach(stringsinstrArray) { if(s.Length>maxLength) { maxLength=s.Length; } } //确定字符的整数范围 intrangeStart=_myCharSet[0]; intrangeEnd=_myCharSet[0]; foreach(charchin_myCharSet) { if(ch<rangeStart) rangeStart=ch; if(ch>=rangeEnd) rangeEnd=ch+1; } //也要为"空字符"分配一个桶，其索引为0 intbucketCount=rangeEnd-rangeStart+1; LinkedList<string>[]buckets=newLinkedList<string>[bucketCount]; //初始化所有的桶 for(inti=0;i<buckets.Length;i++) { buckets[i]=newLinkedList<string>(); } //从最后一个字符开始排序 intcurrentIndex=maxLength-1; while(currentIndex>=0) { foreach(stringtheStringinstrArray) { //如果超出索引，返回''字符(default(char)) charch=theString.ElementAtOrDefault(currentIndex); if(ch==default(char)) {//"空字符"的处理 buckets[0].AddLast(theString); } else {//将字符映射到桶 intindex=ch-rangeStart+1; buckets[index].AddLast(theString); } } //从桶里依次取回字符串，完成一趟排序 inti=0; foreach(LinkedList<string>bucketinbuckets) { while(bucket.Count>0) { strArray[i++]=bucket.First(); bucket.RemoveFirst(); } } currentIndex--; } }

稍作”改良”

用作确定字符的整数范围的代码略显蛋疼，而且根据字符集来看，并不是区间内所有的整数对应的字符都可能出现，因此会有这样的情况：我们给某些根本不会出现的字符分配了桶，这纯属浪费。我们可以用一个字典(散列)来记录字符和它的桶之间的映射。于是有了下面的代码。

privateDictionary<char,int>_charOrderDict= newDictionary<char,int>(_myCharSet.Length); voidBuildCharOrderDict() { char[]sortedCharSet=_myCharSet.ToArray(); //使用默认的比较器排序 Array.Sort(sortedCharSet); //为"空字符"单独创建映射 _charOrderDict.Add(default(char),0); for(inti=0;i<sortedCharSet.Length;i++) { //保存的是字符及其对应的桶的索引 _charOrderDict.Add(sortedCharSet[i],i+1); } }

也可以不用默认的字符排序来作为映射，而完全自己定义字符之间的大小关系。下面是调整后的代码：

voidStringRadixSort(string[]strArray) { if(strArray==null ||strArray.Length==0 ||strArray.Contains(null)) { return; } //获得字符串的最大长度 intmaxLength=0; foreach(stringsinstrArray) { if(s.Length>maxLength) { maxLength=s.Length; } } //为每一个字符(包括空字符'')分配一个桶 //"空字符"索引应为0 intbucketCount=_myCharSet.Length+1; LinkedList<string>[]buckets=newLinkedList<string>[bucketCount]; //初始化所有的桶 for(inti=0;i<buckets.Length;i++) { buckets[i]=newLinkedList<string>(); } //从最后一个字符开始排序 intcurrentIndex=maxLength-1; while(currentIndex>=0) { foreach(stringtheStringinstrArray) { //如果超出索引，返回''字符(default(char)) charch=theString.ElementAtOrDefault(currentIndex); //根据字符顺序的定义查询字符 intindex=_charOrderDict[ch]; buckets[index].AddLast(theString); } //从桶里依次取回字符串，完成一趟排序 inti=0; foreach(LinkedList<string>bucketinbuckets) { while(bucket.Count>0) { strArray[i++]=bucket.First(); bucket.RemoveFirst(); } } currentIndex--; } }

Now,itworks!如果采用的快速排序来做，其时间复杂度为O(n∗logn)O(n∗logn)。表面上看，基数排序更好，不过严格来说，基数排序的时间复杂度应该是O(k∗n)O(k∗n)，其中k和字符串长度正相关。此时两种算法的比较可以通过比较k和lognlogn的比较结果近似得出。如果字符串的长度很长，即k很大，而输入规模n不大的时候，就会有k>lognlogn，此时快速排序反而更有优势。反之，则基数排序可能更优。

最后…

杯具的是，当我扩大字符集，将键盘上所有字符都加进去后，发现基数排序的结果和Array.Sort(string[]方法的排序结果并不一样。仔细观察资源管理器对文件名的排序，才发现其字符串排序的规则要复杂的多，并非简单的比较字符。查询相关资料后发现，字符串的排序甚至还要考虑区域文化的影响，即使都是拉丁字母，不同地区的排序规则都可能不一样，因此，使用基数排序实现的字符串排序算法好像并无多大实用价值<T-T>。

您可能感兴趣的文章:C#实现冒泡排序算法的代码示例c#快速排序算法C#排序算法之快速排序C#排序算法之堆排序c#冒泡排序算法(BubbleSort)附实例代码逐步讲解快速排序算法及C#版的实现示例C#七大经典排序算法系列（上）C#几种排序算法C#实现的二维数组排序算法示例c#实现最简洁的快速排序（你绝对可以看懂）

C#调用存储过程详解(带返回值、参数输入输出等)

一张图上述就是C#学习教程：C#中使用基数排序算法对字符串进行排序的示例分享的全部内容，如果对大家有所用处且需要了解更多关于C#学习教程，希望大家多多关注—计算机技术网(www.ctvol.com)!