混合数字和字符串的排序

Question

我有一个字符串列表，其中包含字母或最多为两位数字的整数的字符串表示。 它们需要按字母顺序或（当它实际上是整数时）其表示的数值进行排序。

例如：

IList<string> input = new List<string>()
    {"a", 1.ToString(), 2.ToString(), "b", 10.ToString()};

input.OrderBy(s=>s)
  // 1
  // 10
  // 2
  // a
  // b

我所希望的是什么

  // 1
  // 2
  // 10
  // a
  // b

我有一个想法，涉及解析并尝试格式化它，然后如果成功解析，使用我的自定义字符串格式化程序使其具有前导零。我希望有更简单和高效的方法。

编辑
最终我编写了一个IComparer，并将其放入我的Utils库中以供日后使用。
在此过程中，我还添加了对double类型的支持。

public class MixedNumbersAndStringsComparer : IComparer<string> {
    public int Compare(string x, string y) {
        double xVal, yVal;

        if(double.TryParse(x, out xVal) && double.TryParse(y, out yVal))
            return xVal.CompareTo(yVal);
        else 
            return string.Compare(x, y);
    }
}

//Tested on int vs int, double vs double, int vs double, string vs int, string vs doubl, string vs string.
//Not gonna put those here
[TestMethod]
public void RealWorldTest()
{
    List<string> input = new List<string>() { "a", "1", "2,0", "b", "10" };
    List<string> expected = new List<string>() { "1", "2,0", "10", "a", "b" };
    input.Sort(new MixedNumbersAndStringsComparer());
    CollectionAssert.AreEquivalent(expected, input);
}

- Boris Callens

Answer 1

我想到了两种方法，不确定哪种更有效率。实现一个自定义的IComparer：

class MyComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        int xVal, yVal;
        var xIsVal = int.TryParse( x, out xVal );
        var yIsVal = int.TryParse( y, out yVal );

        if (xIsVal && yIsVal)   // both are numbers...
            return xVal.CompareTo(yVal);
        if (!xIsVal && !yIsVal) // both are strings...
            return x.CompareTo(y);
        if (xIsVal)             // x is a number, sort first
            return -1;
        return 1;               // x is a string, sort last
    }
}

var input = new[] {"a", "1", "10", "b", "2", "c"};
var e = input.OrderBy( s => s, new MyComparer() );

或者将序列分割成数字和非数字，然后对每个子组进行排序，最后连接排序后的结果；类似这样：

var input = new[] {"a", "1", "10", "b", "2", "c"};

var result = input.Where( s => s.All( x => char.IsDigit( x ) ) )
                  .OrderBy( r => { int z; int.TryParse( r, out z ); return z; } )
                  .Union( input.Where( m => m.Any( x => !char.IsDigit( x ) ) )
                               .OrderBy( q => q ) );

- LBushkin

---

您的 IComparer 没有按正确（字母）顺序返回非数字字符串。而您的 LINQ 查询则可以。 - LukeH

我在 OP 中添加了我的结束代码。还注意到字符串的问题。此外，我尝试在每次解析之前进行短路计算。不知道是否会有很多性能影响，但重新排列它们需要的努力正好与测试它所需的努力相同 ;) - Boris Callens

代码变得更短了。通过应用短路系统（荷兰语字面意思为“Kortsluitingsprincipe”），我只进行必要的尝试解析。 - Boris Callens

Answer 2

也许你可以采用更通用的方法，使用类似于C#实现的自然排序算法，更多信息请参考这里。

- Nathan Baulch

---

非常酷，我刚刚还发现了一个 Delphi 封装器，链接是 http://irsoft.de/web/strnatcmp-and-natsort-for-delphi。 - Peter Turner

这种方法并不适用于所有情况。假设你有以下项目列表：“0 / 30”、“0 / 248”、“0 / 496”、“0 / 357.6”。在排序后，这个顺序将被保留，这可能不是你所期望的结果。 - AH.

不要粘贴一些url，你应该在这里添加代码以避免死链接。现在这个答案不过是一条评论。 - Toshi

Answer 3

我有一个类似的问题并且来到了这里：对具有数字后缀的字符串进行排序，如下面的例子所示。

原文：

"Test2", "Test1", "Test10", "Test3", "Test20"

默认排序结果：

"Test1", "Test10", "Test2", "Test20", "Test3"

期望的排序结果：

"Test1", "Test2", "Test3, "Test10", "Test20"

我最终使用了一个自定义的比较器：

public class NaturalComparer : IComparer
{

    public NaturalComparer()
    {
        _regex = new Regex("\\d+$", RegexOptions.IgnoreCase);
    }

    private Regex _regex;

    private string matchEvaluator(System.Text.RegularExpressions.Match m)
    {
        return Convert.ToInt32(m.Value).ToString("D10");
    }

    public int Compare(object x, object y)
    {
        x = _regex.Replace(x.ToString(), matchEvaluator);
        y = _regex.Replace(y.ToString(), matchEvaluator);

        return x.CompareTo(y);
    }
}   

使用方法：

var input = new List<MyObject>(){...};
var sorted = input.OrderBy(o=>o.SomeStringMember, new NaturalComparer());

HTH ;o)

- mike

---

这正是我需要的，但我的字符串列表在列表类型的对象内部，您能否展示如何使用此方法？ - Aakash Bashyal

@AakashBashyal，我在上面的答案中添加了一个示例。 - mike

仅创建一个列表类型对象会对列表中的项目进行排序吗？ - Aakash Bashyal

但是在 x = _regex.Replace(x.ToString, matchEvaluator); 上出现了错误，错误信息为 参数 1：无法从 '方法组' 转换为 '字符串'。 - Aakash Bashyal

@AakashBashyal 对不起，是我的错。我修复了代码。谢谢！ - mike

Answer 4

使用另一个重载的 OrderBy，它接受一个 IComparer 参数。然后，您可以实现自己的 IComparer，使用 int.TryParse 来判断是否为数字。

- Christian Hayter

Answer 5

我认为你可以使用正则表达式（假设所有内容都是整数）将值拆分，然后将它们重新组合在一起。

//create two lists to start
string[] data = //whatever...
List<int> numbers = new List<int>();
List<string> words = new List<string>();

//check each value
foreach (string item in data) {
    if (Regex.IsMatch("^\d+$", item)) {
        numbers.Add(int.Parse(item));
    }
    else {
        words.Add(item);
    }
}

然后，您可以对这两个列表进行排序，然后以任何格式将它们合并在一起。

- hugoware

---

是的，这比我的方法简单。+1 - Jonathan Rupp

Answer 6

你可以直接使用Win32 API提供的函数：

[DllImport ("shlwapi.dll", CharSet=CharSet.Unicode, ExactSpelling=true)]
static extern int StrCmpLogicalW (String x, String y);

像其他人展示的那样，可以从IComparer中调用它。

- Skizz

Answer 7

public static int? TryParse(string s)
{
    int i;
    return int.TryParse(s, out i) ? (int?)i : null;
}

// in your method
IEnumerable<string> input = new string[] {"a", "1","2", "b", "10"};
var list = input.Select(s => new { IntVal = TryParse(s), String =s}).ToList();
list.Sort((s1, s2) => {
    if(s1.IntVal == null && s2.IntVal == null)
    {
        return s1.String.CompareTo(s2.String);
    }
    if(s1.IntVal == null)
    {
        return 1;
    }
    if(s2.IntVal == null)
    {
        return -1;
    }
    return s1.IntVal.Value.CompareTo(s2.IntVal.Value);
});
input = list.Select(s => s.String);

foreach(var x in input)
{
    Console.WriteLine(x);
}

它仍然进行转换，但每个项目只进行一次。

- Jonathan Rupp

Answer 8

您可以使用自定义比较器 - 排序语句将会是：

var result = input.OrderBy(s => s, new MyComparer());

其中MyComparer的定义如下：

public class MyComparer : Comparer<string>
{
    public override int Compare(string x, string y)
    {

        int xNumber;
        int yNumber;
        var xIsNumber = int.TryParse(x, out xNumber);
        var yIsNumber = int.TryParse(y, out yNumber);

        if (xIsNumber && yIsNumber)
        {
            return xNumber.CompareTo(yNumber);
        }
        if (xIsNumber)
        {
            return -1;
        }
        if (yIsNumber)
        {
            return 1;
        }
        return x.CompareTo(y);
    }
}

虽然这可能看起来有点啰嗦，但它将排序逻辑封装成了一个合适的类型。如果您希望，可以轻松地将Comparer提交给自动化测试（单元测试）。它也是可重用的。

（可能可以使算法更清晰一些，但这是我能够快速组合的最好的方法。）

- Mark Seemann

Answer 9

使用Schwartzian Transform来执行O(n)转换！

private class Normalized : IComparable<Normalized> {
  private readonly string str;
  private readonly int val;

  public Normalized(string s) {
    str = s;

    val = 0;
    foreach (char c in s) {
      val *= 10;

      if (c >= '0' && c <= '9')
        val += c - '0';
      else
        val += 100 + c;
    }
  }

  public String Value { get { return str; } }

  public int CompareTo(Normalized n) { return val.CompareTo(n.val); }
};

private static Normalized In(string s) { return new Normalized(s); }
private static String Out(Normalized n) { return n.Value; }

public static IList<String> MixedSort(List<String> l) {
  var tmp = l.ConvertAll(new Converter<String,Normalized>(In));
  tmp.Sort();
  return tmp.ConvertAll(new Converter<Normalized,String>(Out));
}

- Greg Bacon

---

据我所知，这并不比我发布的更简单。它可能更高效，但把性能放在简单性之上并不是至关重要的。 - Boris Callens

Answer 10

您还可以在某种程度上“作弊”。根据您对问题的描述，您知道长度为2的任何字符串都将是一个数字。因此，只需对长度为1的所有字符串进行排序。然后按长度为2对所有字符串进行排序。然后进行一系列交换以重新排列字符串的顺序。基本上，该过程将按如下方式工作：（假设您的数据在数组中。）

第1步：将所有长度为2的字符串推送到数组的末尾。跟踪您拥有多少个。

第2步：原地对长度为1和长度为2的字符串进行排序。

第3步：二进制搜索“a”，它将位于两个半部分的边界上。

第4步：根据需要交换您的两位数字字符串与字母。

话虽如此，虽然此方法有效，不涉及正则表达式，并且不试图将非int值解析为int-但我不建议这样做。您将编写比已建议的其他方法更多的代码。它掩盖了您尝试做什么的重点。如果您突然得到两个字母字符串或三个数字字符串，则无法正常工作。等等。我只是包括它以展示您如何以不同的方式看待问题并提出替代解决方案。

- Rob Rolnick