快捷導(dǎo)航

C#中使用基數(shù)排序算法對(duì)字符串進(jìn)行排序的示例

更新時(shí)間：2016年06月08日 19:10:51 投稿：goldensun

Radix Sort基數(shù)排序是非比較型的排序算法,其時(shí)間復(fù)雜度是O(k·n),n為元素個(gè)數(shù),為數(shù)字位數(shù),這里我們就來看一下C#中使用基數(shù)排序算法堆字符串進(jìn)行排序的示例

開始之前

假設(shè)最長(zhǎng)字符串的長(zhǎng)度是L，以L作為輸入的長(zhǎng)度，然后假定所有的字符串都"補(bǔ)齊"到此長(zhǎng)度，這個(gè)補(bǔ)齊只是邏輯上的，我們可以假想有一種"空字符"，它小于任何其它字符，用此字符補(bǔ)齊所有長(zhǎng)度不足的字符串。例如：最長(zhǎng)的字符串長(zhǎng)度為9，有一個(gè)字符串A長(zhǎng)度為6，那么當(dāng)比較第7位字符的時(shí)候，我們讓A[7]為"空字符"。

如果要包含所有的字符似乎并不容易，我們先定義一個(gè)字符集，待排序字符串中的所有字符都包含在這個(gè)字符集里

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

再來一個(gè)生成隨機(jī)字符串的方法(C#實(shí)現(xiàn))：

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++)
  {
    //先隨機(jī)確定一個(gè)長(zhǎng)度
    len = _random.Next(minLength, maxLength);
    for (int j = 0; j < len; j++)
    {
      //隨機(jī)選取一個(gè)字符
      sb.Append(_myCharSet[_random.Next(_myCharSet.Length)]);
    }
    strs[i] = sb.ToString();
    sb.Clear();
  }
  return strs;
}

這里按照字符的整數(shù)表示來確定桶的范圍，再為"空字符"準(zhǔn)備一個(gè)桶。為了表示"空字符"這個(gè)特例，這里用default(char)，即'\0'表示它，因?yàn)楫?dāng)調(diào)用string.ElementAtOrDefault(int)方法時(shí)，如果超出索引會(huì)返回'\0'。

初級(jí)版本(C#)

void StringRadixSort(string[] strArray)
{
  if (strArray == null
    || strArray.Length == 0
    || strArray.Contains(null))
  {
    return;
  }
 
  //獲得字符串的最大長(zhǎng)度
  int maxLength = 0;
  foreach (string s in strArray)
  {
    if (s.Length > maxLength)
    {
      maxLength = s.Length;
    }
  }
 
  //確定字符的整數(shù)范圍
  int rangeStart = _myCharSet[0];
  int rangeEnd = _myCharSet[0];
  foreach (char ch in _myCharSet)
  {
    if (ch < rangeStart)
      rangeStart = ch;
    if (ch >= rangeEnd)
      rangeEnd = ch + 1;
  }
 
  //也要為"空字符"分配一個(gè)桶，其索引為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>();
  }
 
  //從最后一個(gè)字符開始排序
  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--;
  }
}

稍作"改良"

用作確定字符的整數(shù)范圍的代碼略顯蛋疼，而且根據(jù)字符集來看，并不是區(qū)間內(nèi)所有的整數(shù)對(duì)應(yīng)的字符都可能出現(xiàn)，因此會(huì)有這樣的情況：我們給某些根本不會(huì)出現(xiàn)的字符分配了桶，這純屬浪費(fèi)。我們可以用一個(gè)字典(散列)來記錄字符和它的桶之間的映射。于是有了下面的代碼。

private Dictionary<char, int> _charOrderDict = 
        new Dictionary<char, int>(_myCharSet.Length);
void BuildCharOrderDict()
{
  char[] sortedCharSet = _myCharSet.ToArray();
  //使用默認(rèn)的比較器排序
  Array.Sort(sortedCharSet);
  //為"空字符"單獨(dú)創(chuàng)建映射
  _charOrderDict.Add(default(char), 0);
  for (int i = 0; i < sortedCharSet.Length; i++)
  {
    // 保存的是字符及其對(duì)應(yīng)的桶的索引
    _charOrderDict.Add(sortedCharSet[i], i + 1);
  }
}

也可以不用默認(rèn)的字符排序來作為映射，而完全自己定義字符之間的大小關(guān)系。下面是調(diào)整后的代碼：

void StringRadixSort(string[] strArray)
{
  if (strArray == null
    || strArray.Length == 0
    || strArray.Contains(null))
  {
    return;
  }
  //獲得字符串的最大長(zhǎng)度
  int maxLength = 0;
  foreach (string s in strArray)
  {
    if (s.Length > maxLength)
    {
      maxLength = s.Length;
    }
  }
 
  //為每一個(gè)字符(包括空字符'\0')分配一個(gè)桶
  //"空字符"索引應(yīng)為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>();
  }
 
  //從最后一個(gè)字符開始排序
  int currentIndex = maxLength - 1;
  while (currentIndex >= 0)
  {
    foreach (string theString in strArray)
    {
      //如果超出索引，返回'\0'字符(default(char))
      char ch = theString.ElementAtOrDefault(currentIndex);
      //根據(jù)字符順序的定義查詢字符
      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! 如果采用的快速排序來做，其時(shí)間復(fù)雜度為O(n∗logn)O(n∗logn)。表面上看，基數(shù)排序更好，不過嚴(yán)格來說，基數(shù)排序的時(shí)間復(fù)雜度應(yīng)該是O(k∗n)O(k∗n)，其中k和字符串長(zhǎng)度正相關(guān)。此時(shí)兩種算法的比較可以通過比較k和lognlogn的比較結(jié)果近似得出。如果字符串的長(zhǎng)度很長(zhǎng)，即k很大，而輸入規(guī)模n不大的時(shí)候，就會(huì)有k>lognlogn，此時(shí)快速排序反而更有優(yōu)勢(shì)。反之，則基數(shù)排序可能更優(yōu)。

最后...

杯具的是，當(dāng)我擴(kuò)大字符集，將鍵盤上所有字符都加進(jìn)去后，發(fā)現(xiàn)基數(shù)排序的結(jié)果和Array.Sort(string[]方法的排序結(jié)果并不一樣。仔細(xì)觀察資源管理器對(duì)文件名的排序，才發(fā)現(xiàn)其字符串排序的規(guī)則要復(fù)雜的多，并非簡(jiǎn)單的比較字符。查詢相關(guān)資料后發(fā)現(xiàn)，字符串的排序甚至還要考慮區(qū)域文化的影響，即使都是拉丁字母，不同地區(qū)的排序規(guī)則都可能不一樣，因此，使用基數(shù)排序?qū)崿F(xiàn)的字符串排序算法好像并無多大實(shí)用價(jià)值<T-T>。

您可能感興趣的文章: