開始之前
假設最長字符串的長度是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>。
新聞熱點
疑難解答
