开始之前
假设最长字符串的长度是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>。
我的代码中有什么错误? 给定一个由小写字母组成的字符串,请按升序排列其所有字母。 输入:输入的第一行包含T,表示测试用例的数量。然后是每个测试用例的描述。测试用例的第一行包含表示字符串长度的正整数N。第二行包含字符串。 输出:对于每个测试用例,输出排序后的字符串。 约束条件: 对于输入: 输出: 预期输出:
对于这个项目,我得到了一个字符串数组和一个整数数组。int[1]是字符串[1]的排名。我需要使用mergesort按1到n的顺序对int数组进行排序,我在下面已经完成了这项工作。但是当int数组被移动时,我还需要切换字符串数组的位置,以便它们都被排序,如果这有意义的话?我不知道我的编码有什么问题,甚至我的想法是否真的有效,但我一直在stringSorted[k]=stringRight[j]上得到
本文向大家介绍JAVA使用TreeMap对字符串进行排序,包括了JAVA使用TreeMap对字符串进行排序的使用技巧和注意事项,需要的朋友参考一下 这篇文章主要介绍了JAVA使用TreeMap对字符串进行排序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 题目要求: 给出一个字符串:fjdjskgfhbsjkgjnsrgnaHNGKEURHGAS
问题内容: 我有一个包含多个数组的数组,我想根据这些数组中的某个字符串对数组进行排序。 如何按名称排序,以便 阿尔伯特排 在首位, 齐默尔曼排 在最后? 我知道如果可以使用整数进行排序,但是字符串使我毫无头绪,该怎么办。 谢谢您帮忙!:) 问题答案: 这可以通过将支持函数作为参数传递给方法调用来实现。 像这样:
本文向大家介绍Swift对字符串数组进行排序,包括了Swift对字符串数组进行排序的使用技巧和注意事项,需要的朋友参考一下 例子 3.0 最简单的方法是使用sorted(): 或者 sort() 您可以将闭包作为排序参数: 尾随闭包的替代语法: 但是,如果数组中的元素不一致,则会出现意外结果: 要解决此问题,请对元素的小写版本进行排序: 或者import Foundation使用NSString的
问题内容: 允许用户使用字符串数组进行演奏。他们可以将字符串添加到数组中,从数组中删除字符串,在数组中搜索字符串,最终他们将能够对数组进行排序。排序使我很困惑。我尝试了几种不同的方法。第一种方法是将数组转换为ArrayList并使用Collections对ArrayList进行排序,然后将其转换回静态类数组。没用 我尝试的第二种方法是遍历数组,并尝试仅对用户添加的字符串进行排序,而不是对数组中的所
我主要是一个VB.NET程序员,对VTL(Velocity Template Language)非常陌生。我目前正试图定制一个应用程序,使用Velocity模板和Jython。 我在一个现有文件中有以下VTL代码。以下代码从一个JSON文件中获得一些键值对,并将它们以一个简洁的表形式输出到浏览器: 我可以显示$keyset数组: 我试图做的是按字母顺序对$keyset数组中的字符串进行排序。 我尝
问题内容: 我创建了一个sqlite数据库,该数据库具有一个存储温度值的表。第一次将温度值以升序写入数据库。然后,我将数据库中的温度值读取到一个列表中,然后将该列表添加到组合框中以选择温度- 效果很好。 结果列表为: 然后,我向数据库添加一个新的温度值,例如“ 33”。 它被附加到表的末尾。如果我现在阅读温度,列表将变为: 如果我做或,最终的结果是 有什么简单的方法可以按升序对列表进行排序,以便得