C#中應用基數排序算法對字符串停止排序的示例

C#中應用基數排序算法對字符串停止排序的示例。本站提示廣大學習愛好者：（C#中應用基數排序算法對字符串停止排序的示例）文章只能為提供參考，不一定能成為您想要的結果。以下是C#中應用基數排序算法對字符串停止排序的示例正文

開端之前

假定最長字符串的長度是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>。