Сортировка смешанных чисел и строк - PullRequest
15 голосов
/ 23 июня 2009

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

Пример:

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

Ответы [ 10 ]

20 голосов
/ 23 июня 2009

Два способа приходят на ум, не уверен, что является более производительным. Реализуйте пользовательский 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 ) );
12 голосов
/ 23 июня 2009

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

3 голосов
/ 23 июня 2009

Используйте другую перегрузку OrderBy, которая принимает параметр IComparer.

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

2 голосов
/ 23 июня 2009

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

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

и позвоните по номеру IComparer, как показали другие.

2 голосов
/ 23 июня 2009

Я бы сказал, что вы можете разделить значения с помощью выражения 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);
    }
}

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

1 голос
/ 01 февраля 2017

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

Оригинал:

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

HTH; о)

1 голос
/ 23 июня 2009

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

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

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

Шаг 2: Сортировка на месте строк длины 1 и строк длины 2.

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

Шаг 4: Поменяйте местами две цифры строки с нужными буквами.

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

1 голос
/ 23 июня 2009

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

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

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

1 голос
/ 23 июня 2009
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);
}

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...