使用 IComparer 为人类排序字符串
4.53/5 (9投票s)
以人类期望的方式对列表进行排序
引言
自定义的 IComparer 对象可用于为 .NET 排序算法提供字符串排序的替代策略。此处提供的 IComparer 旨在像人类一样解释字符串，而不是计算机严格的字典序排序。
背景
CodingHorror 上的一篇近期文章指出，“几乎所有编程语言中的默认排序函数都非常不适合人类使用。” 计算机依靠对正在排序的字符串逐个字符进行严格比较，但人类并不是这样思考字符串的。
在人类的思维中，我们会将字符串分解成块，将其中一些块识别为文本（可以逐字符比较），而将另一些块视为数字。数字块应该按值排序，但标准的排序算法并未考虑到这一点。
| 考虑一位摄影师命名他的文件。如果他（假设他的思维方式与普通人一样，而不是像我们程序员那样“扭曲”）将文件命名如下，这完全是合理的： | 如果我们的摄影师将这些文件输入到典型的软件中进行排序，结果将是完全不可接受的： |
|
|
因此，我们的目标是改革计算机反社会的方式，使其更能让用户感到舒适。
Using the Code
.NET Framework 极大地简化了这一目标。微软自身也为 .NET 平台上的软件“人性化”做出了努力：例如内置的全球化支持。更具体地说，有助于我们实现目标的设计原则是允许许多默认行为根据开发者的意图进行定制，例如已实现 Provider 模式的许多领域。
在我们的例子中，我们可以采用自定义的 IComparer 来为集合中字符串的排序提供一种替代方法。有了此处提供的 IComparer，使用它而不是内置的字符串比较是微不足道的。
这段代码来自该库的演示应用程序。
List<string> n = new List<string>(lbInputList.Items.Count);
foreach (string s in lbInputList.Items)
{
n.Add(s);
}
n.Sort(new NaturalComparer());
这段代码大部分用于从列表框创建和填充 List。实际使用自定义 IComparer 的只有这段代码的最后一行。
List.Sort() 方法提供了几个重载。常见的那个（无参数）使用内置的字符串比较。但在这里，我们创建了一个实现 IComparer 接口的替代比较器实例，并将其传递给 Sort。
关注点
NaturalComparer 通过实现 IComparer 接口，能够为 sort 方法提供字符串排序服务。其设计主要有三个部分：将每个字符串分解成块、解释每个块的值以及比较每个块。
实现 IComparer
实际上，这段代码实现了两个接口：用于向后兼容的 .NET 1.0 中的旧版 IComparer，以及更类型安全的 IComparer<string>。前者通过显式接口定义被“隐藏”，并将任何调用传递给特定类型的版本。该接口仅需要一个方法：
int Compare(string left, string right) { ... }
返回的 int 应具有以下三个值之一：
0- 值在列表中排序到相同位置（值得注意的是，这不表示两个值相等）。-1- 左参数“较小” - 在升序列表中，它排在前面。1- 左参数“较大” - 在升序列表中，它排在后面。
因此，我们实现此方法的任务是找到一种魔法，能够判断我们假设的人类会认为一个字符串比另一个大还是小。
分割字符串
我们想模仿（大概）人类的思维：识别字符串中的离散信息块，然后依次比较它们。最大的挑战在于确定什么构成一个独立的块。
我认为空格可以分隔块，但空格的数量无关紧要。事实上，使用比例字体，即使有意识地尝试，也很难确定有多少个空格（或制表符！）。我发现我不期望排序由标点符号和其他非单词或数字字符的排序来确定，所以我将所有这些“噪音”也考虑在内。
简而言之，字符串被分解为单词块和数字块。
与任何实际的编程问题一样，有很多方法可以解决。我最初考虑采用更面向对象的方法，使用一个状态机来扫描每个字符串，组装并返回文本标记和数字标记，它们都派生自一个基标记类。这可能更有效，因为它只需要扫描必要的最短距离来找到差异；在许多情况下，不需要考虑字符串的末尾。然而，它给代码（至少是你需要自己编写的代码）带来的复杂性太大了，超出了我愿意投入的工作。
相反，我只使用正则表达式来分割每个字符串。我开发的正则表达式查找由字母或数字组成的组，中间是其他被忽略的“垃圾”。
由于使用它的目的是为了排序列表，预期比较会调用很多次（每次比较两次，并且对于大多数算法，会有 N log(n) 次比较），所以我编译了正则表达式，并将其保存为类中的 static 字段。正则表达式的初始编译在启动时需要一些时间，但在排序任何可观大小的字符串时可能会物有所值。
private static Regex sRegex;
static NaturalComparer()
{
sRegex = new Regex(@"[\W\.]*([\w-[\d]]+|[\d]+)", RegexOptions.Compiled);
}
当被要求进行比较时，我们让正则表达式返回来自两个字符串的所有匹配项。
MatchCollection leftmatches = sRegex.Matches(left);
MatchCollection rightmatches = sRegex.Matches(right);
然后，我们遍历左侧字符串的每个匹配项，同时在右侧字符串中使用 Enumerator 作为光标来记住我们的位置。实际上，我们希望不遍历整个字符串；一旦我们能明确地说一个字符串应该排在另一个前面，我们就返回该信息。
如果一个字符串比另一个字符串先耗尽匹配项，则先耗尽的那个被视为“较小”。我们可以通过完成 foreach 循环但右侧仍至少有一个匹配项（通过尝试移动枚举器到下一项来确定）来判断左侧字符串先耗尽。反之，如果在循环过程中右侧字符串的枚举器无法再移动，则右侧字符串已耗尽。
IEnumerator enrm = rightmatches.GetEnumerator();
foreach (Match lm in leftmatches)
{
if (!enrm.MoveNext())
{
// the right-hand string ran out first, so is considered "less-than" the left
return 1;
}
Match rm = enrm.Current as Match;
int tokenresult = CompareTokens(CapturedStringFromMatch(lm),
CapturedStringFromMatch(rm));
if (tokenresult!=0)
{
return tokenresult;
}
}
// the lefthand matches are exhausted;
// if there is more, then left was shorter, i.e. lessthan
// if there's no more left in the righthand, then they were all equal
return enrm.MoveNext() ? -1 : 0;
（顺便说一句，人们想知道为什么 MatchCollection 只能提供一个旧式的非类型安全枚举器，而不是一个 Enumerator<Match>。）
正则表达式的优缺点
如果我们选择了面向对象的方法，我们可以为字符串的分割添加额外的智能。但使用更简单的正则表达式方法，我们被迫接受一些妥协。
一种妥协是数字的解释方式。小数点被视为分隔符，而不是小数点。这会影响处理十进制数的能力（尽管我稍后会看到一个hack 解决方法）。但是，通过不正确地处理十进制数，我们获得了正确处理版本号（例如 1.02.1.68）的能力。
对单词分隔字符的处理本可以更好。连字符和撇号等问题尚未解决。有可能创建一个（更复杂得多的）正则表达式来处理其中一些问题。然而，这些选择必然是语言相关的，所以我选择不构建一个仅限英语的解决方案。
无论如何，正则表达式都非常通用。如果您的应用程序需要略有不同的分割方式，我鼓励您尝试正则表达式。
比较块
给定两个块（分别来自两个字符串），首先要做的是确定它们代表数字还是纯文本。这通过尝试将匹配的字符串解析为 double 来完成。我使用 double 不是因为十进制数（记住，我的正则表达式不处理这个），而是因为数字集可能描述一个非常大的数字。
leftisnum = double.TryParse(left, out leftval);
rightisnum = double.TryParse(right, out rightval);
只有当两个块都代表数字时，才需要进行数字比较。如果只有一个代表数字，那么数字块排在前面。如果都不是（即都是文本），则使用普通的字符串比较。
实际的数字比较需要一些解释。如果值不同，则行为符合预期。但是，如果字符串表示相同的值，我们并不一定认为这些值是等价的。因为 1 和 001 都评估为相同的值，但在某些情况下可能意味着截然不同的东西，所以有一个额外的检查。
考虑比较字符串 2.1 和 2.001；显然，我们希望后者评估为更小。但是，当块比较发生时，我们无法看到前面的“2.”。我的 hack 解决方法是简单地假设具有等效值但长度不同的数字是不同的。具体来说，在其他条件相同的情况下，较长的数字被认为是较小的值。这个规则正确地评估了这个例子。
if (leftisnum)
{
if (!rightisnum)
{
return -1;
}
// they're both numeric
if (leftval<rightval)
{
return -1;
}
if (rightval<leftval)
{
return 1;
}
// if values are same, this might be due to leading 0s.
// Assuming this, the longest string would indicate more leading 0s
// which should be considered to have lower value
return Math.Sign(right.Length - left.Length);
}
结论
确定人类是否会把一个字符串排在另一个前面是一个模糊的问题，可能没有确定的正确答案。但是开发一个合理的算法并不困难。一旦有了这个算法，.NET Framework 的设计使得您的应用程序可以轻松地以普通人觉得更直观的方式对字符串进行排序。
这是一个值得追求的目标。计算机可以做惊人的事情，但当今的尖端技术在计算机可用性方面仍然是一种悲哀。我相信，在这方面投入精力比当今软件开发的许多方向都更有价值。
致谢
- Effective C#: Bill Wagner 的《50 种具体改进 C# 的方法》
对IComparer及其相关接口IComparable的实现进行了精彩的讨论。而这仅仅是书中 50 篇文章中的一篇。每个 C# 开发者不仅应该阅读这本书，而且应该将其放在手边。 - Roy Osherove 的Regulazy
一个用于理解和测试正则表达式的绝佳工具。 - Jeff Atwood 的CodingHorror
持续讨论新技术和软件开发世界的失败之处。
历史
- 2007-12-31（无代码更改）
- 删除了关于
Compare返回值文档缺失的注释，因为有人指出了文档。
- 删除了关于
- 1.0.1.2 - 2007-12-17
- 错误修复 - 在比较数字和文本时漏掉了一个可能的组合。
- 1.0.0.1 - 2007-12-16
- 首次发布