FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

使用基数排序(Radix Sort)排序字符串

FunctionGHW posted @ 2014年8月21日 16:06 in 算法学习 with tags sort radix sort string sort , 10728 阅读

基数排序(Radix Sort)是 非比较排序算法,其时间复杂度是线性的, 即\(O(n)\)。刚刚接触这个算法的时候,本以为该算法只适合输入时非负整数的情况, 不过最近在整理以前写的排序算法的Demo时,偶然想到该算法应该也可以用于字符串的排序。 根据算法的特点,直观感觉是:待排序字符串应该都是等长的。不过, 只要稍加改造,该算法也可以用于不等长字符串排序。

开始之前

假设最长字符串的长度是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*log n)\)。表面上看,基数排序更好,不过严格来说, 基数排序的时间复杂度应该是\(O(k*n)\),其中k和字符串长度正相关。 此时两种算法的比较可以通过比较k和\(log n\)的比较结果近似得出。 如果字符串的长度很长,即k很大,而输入规模n不大的时候, 就会有k>\(log n\),此时快速排序反而更有优势。反之,则基数排序可能更优。

最后...

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

    String sorting and comparison are language-specific. Even within languages based on the Latin script, there are different composition and sorting rules. Thus do not rely on code points to do proper sorting and string comparison.
引用自:Sorting and String Comparison

如果要在实际生产中排序字符串,还是使用类库提供的通用排序算法吧。

 

  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter