正文

C#中使用基数排序算法对字符串进行排序的示例

︶ㄣSDDLL学院 メ
SDDLL学院V管理员 / 阅读
0708
Radix Sort基数排序是非比较型的排序算法,其时间复杂度是O(k·n),n为元素个数,为数字位数,这里我们就来看一下C#中使用基数排序算法堆字符串进行排序的示例

Radix Sort基数排序是非比较型的排序算法,其时间复杂度是O(k·n),n为元素个数,为数字位数,这里我们就来看一下C#中使用基数排序算法堆字符串进行排序的示例

开始之前

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

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

?
1
2
//字符集
private string _myCharSet = "0123456789qwertyuiopasdfghjklzxcvbnm";

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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#)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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--;
  }
}

稍作"改良"

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
  }
}

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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>。