Sortieren von gemischten Zahlen und Strings

Question

Ich habe eine Liste von Strings, die einen Brief oder eine String-Darstellung eines int (max 2-stellig) enthalten können. Sie müssen entweder alphabetisch sortiert werden oder (wenn es tatsächlich ein int) auf dem numerischen Wert es darstellt.

Beispiel:

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

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

Was ich möchte, ist

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

Ich habe eine Idee Formatierung es die mit dem Versuch, es zu analysieren, dann, wenn es ein erfolgreiches TryParse ist es zu formatieren, mit meinen eigenen benutzerdefinierten stringformatter, um es vorangehende Nullen zu machen. Ich hoffe auf etwas einfacher und performant.

Bearbeiten
Ich landete sie ein IComparer ich für die spätere Verwendung in meine Utils Bibliothek geworfen.
Während ich es war auch ich warf Doppel in der Mischung.

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

Vielleicht könnten Sie mit einem allgemeineren Ansatz gehen und eine Algorithmus wie die C # -Implementierung hier .

Answer 2

Zwei Wege in den Sinn kommen, nicht sicher, welche mehr performant ist. Implementieren Sie eine benutzerdefinierte 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() );

Oder teilen Sie die Sequenz in Zahlen und nicht-Zahlen, dann jede Untergruppe sortieren, schließlich die sortierten Ergebnisse verbinden; so etwas wie:

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

Mit der anderen Überlastung der OrderBy, die einen IComparer Parameter annimmt.

Sie können dann Ihre eigene IComparer implementieren, die int.TryParse verwendet zu sagen, ob es sich um eine Zahl ist oder nicht.

Answer 4

Ich würde sagen, Sie die Werte mit einem RegulaererAusdruck aufteilen könnten (vorausgesetzt, alles ist ein int) und sie dann zusammenschließen.

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

Dann mit beiden Listen können Sie jede von ihnen sortieren und sie dann miteinander verschmelzen zurück in was auch immer Sie das gewünschte Format.

Answer 5

Sie könnten nur Funktion von dem Win32-API bereitgestellt:

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

und es von einem IComparer nennen wie andere gezeigt haben.

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

Es tut immer noch die Umwandlung, aber nur einmal / Stück.

Answer 7

Sie könnten einen benutzerdefinierten comparer verwenden - die Bestellung Aussage wäre dann:

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

wo MyComparer sind wie folgt definiert:

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

Obwohl dies ein bisschen ausführlicher scheinen, kapselt er die Sortierlogik in eine richtige Art. Anschließend können Sie, wenn Sie es wünschen, unterziehen leicht die Comparer automatisierte Tests (Unit-Tests). Es ist auch wiederverwendbar.

(Es kann möglich sein, den Algorithmus etwas klarer zu machen, aber das war die beste, das ich schnell zusammen werfen könnte.)

Answer 8

Sie können auch in einem gewissen Sinn „betrügen“. Auf der Basis Ihrer Beschreibung des Problems, wissen Sie eine beliebige Zeichenfolge der Länge 2 wird eine Zahl sein. So einfach irgendwie alle Strings der Länge 1. Und dann sortiert alle Strings der Länge 2. Und dann tut ein Bündel von Swapping Ihre Strings in der richtigen Reihenfolge neu zu ordnen. Im Wesentlichen wird der Prozess funktioniert wie folgt: (. Vorausgesetzt, Ihre Daten in einem Array)

1. Schritt: Schieben alle Strings der Länge 2 bis zum Ende des Arrays. Der Überblick über wie viele Sie haben.

Schritt 2:. Anstelle Art des Strings der Länge 1 und Strings mit einer Länge von 2

Schritt 3:. Binäre Suche nach ‚a‘, die an der Grenze Ihrer beiden Hälften würden

Schritt 4: Tauschen Sie Ihre zweistelligen Strings mit den Buchstaben wie nötig

.

Das heißt, während dieser Ansatz funktionieren wird, ist nicht mit regulären Ausdrücken, und versucht nicht, nicht-int-Werte als int zu analysieren - ich würde es nicht empfehlen. Sie werden wesentlich mehr Code schreiben als andere Ansätze bereits vorgeschlagen. Es verschleiert den Punkt, was Sie zu tun versuchen. Es funktioniert nicht, wenn Sie plötzlich zwei Buchstaben Strings oder dreistellige Strings erhalten. Etc. Ich bin auch es zu zeigen, wie man anders an Problemen aussehen kann, und kommt mit alternativen Lösungen.

Answer 9

Verwenden Sie einen Schwartzian Trans O (n) Konvertierungen durchführen!

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

Ich hatte ein ähnliches Problem und hier gelandet. Saiten Sortierung, die einen numerischen Suffix wie im folgende Beispiel hat

Original:

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

Standardsortierer:

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

Gewünschtes Ergebnis sortieren:

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

Ich landete mit einem benutzerdefinierten 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; o)