Сортировка смешанных чисел и строк

Question

У меня есть список строк, которые могут содержать букву или строковое представление целого числа (максимум 2 цифры).Их необходимо отсортировать либо в алфавитном порядке, либо (если на самом деле это целое число) по числовому значению, которое оно представляет.

Пример:

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 для дальнейшего использования.
Пока я этим занимался, я также добавил дубли.

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);
}

Answer 1

Возможно, вы могли бы использовать более общий подход и использовать естественная сортировка алгоритм, такой как реализация C# здесь.

Answer 2

На ум приходят два способа, но я не уверен, какой из них более эффективен.Реализуйте собственный 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 ) );

Answer 3

Используйте другую перегрузку OrderBy это требует IComparer параметр.

Затем вы можете реализовать свои собственные IComparer который использует int.TryParse чтобы сказать, число это или нет.

Answer 4

Я бы сказал, что вы могли бы разделить значения, используя RegularExpression (при условии, что все является целым числом), а затем снова соединить их вместе.

//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);
    }
}

Затем с помощью двух списков вы сможете отсортировать каждый из них, а затем снова объединить их в любом формате, который захотите.

Answer 5

Вы можете просто использовать функцию предоставляется Win32 API:

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

и вызвать его из IComparer как показали другие.

Answer 6

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);
}

Он по-прежнему выполняет преобразование, но только один раз/элемент.

Answer 7

Вы можете использовать собственный компаратор - тогда оператор заказа будет таким:

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 автоматическому тестированию (модульному тестированию).Он также многоразовый.

(Возможно, можно было бы сделать алгоритм немного понятнее, но это было лучшее, что я смог быстро собрать.)

Answer 8

Вы также можете в некотором смысле «обмануть».Судя по вашему описанию проблемы, вы знаете, что любая строка длины 2 будет числом.Итак, просто отсортируйте все строки длиной 1.А затем отсортируйте все строки длиной 2.А затем выполните несколько перестановок, чтобы изменить порядок строк в правильном порядке.По сути, процесс будет работать следующим образом:(при условии, что ваши данные находятся в массиве.)

Шаг 1:Поместите все строки длины 2 в конец массива.Отслеживание того, сколько у вас есть.

Шаг 2:На месте отсортируйте строки длины 1 и строки длины 2.

Шаг 3:Двоичный поиск буквы «а», которая находилась бы на границе двух ваших половин.

Шаг 4:При необходимости поменяйте местами двузначные строки с буквами.

Тем не менее, хотя этот подход и работает, он не использует регулярные выражения и не пытается анализировать значения, отличные от целочисленных, как целые — я не рекомендую его.Вам придется писать значительно больше кода, чем при других уже предложенных подходах.Это запутывает суть того, что вы пытаетесь сделать.Это не сработает, если вы внезапно получите двухбуквенные строки или трехзначные строки.И т. д.Я включил его просто для того, чтобы показать, как можно по-другому взглянуть на проблемы и найти альтернативные решения.

Answer 9

Использовать Преобразование Шварца для выполнения преобразований 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));
}

Answer 10

У меня была аналогичная проблема, и я попал сюда:сортировка строк с числовым суффиксом, как в следующем примере.

Оригинал:

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

Результат сортировки по умолчанию:

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

Желаемый результат сортировки:

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

В итоге я использовал собственный Comparer:

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);
    }
}   

ХТХ ;о)