Sắp xếp các số và chuỗi hỗn hợp

Question

Tôi có một danh sách các chuỗi có thể chứa một chữ cái hoặc một chuỗi đại diện của một int (tối đa 2 chữ số). Chúng cần được sắp xếp theo thứ tự bảng chữ cái hoặc (khi nó thực sự là một int) trên giá trị số mà nó đại diện.

Ví dụ:

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

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

Những gì tôi muốn là

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

Tôi có một số ý tưởng liên quan đến định dạng nó với cố gắng để phân tích nó, sau đó nếu nó là một TryParse thành công để định dạng nó với tôi tùy chỉnh stringformatter để làm cho nó có các số 0 trước đó. Tôi hy vọng cho một cái gì đó đơn giản hơn và performant.

Chỉnh sửa
Tôi đã kết thúc việc tạo IComparer I được bán trong thư viện Utils để sử dụng sau này.
Trong khi tôi đang ở đó, tôi đã ném đôi trong hỗn hợp quá.

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ó lẽ bạn có thể sử dụng cách tiếp cận chung hơn và sử dụng thuật toán natural sorting như triển khai C# here.

Answer 2

Tôi muốn bạn có thể chia các giá trị bằng RegularExpression (giả sử mọi thứ là int) và sau đó tham gia lại với nhau.

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

Sau đó, với hai danh sách, bạn có thể sắp xếp từng danh sách và sau đó hợp nhất lại với nhau theo bất kỳ định dạng nào bạn muốn.

Answer 3

Sử dụng quá tải khác của OrderBy có thông số IComparer.

Sau đó, bạn có thể thực hiện IComparer riêng của mình sử dụng int.TryParse để biết đó có phải là số hay không.

Answer 4

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

Nó vẫn thực hiện chuyển đổi, nhưng chỉ một lần/mục.

Answer 5

Hai cách cần lưu ý, không chắc chắn cách nào hiệu quả hơn. Triển khai IComparer tùy chỉnh:

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

Hoặc phân chia từng số và không phải số, sau đó sắp xếp từng nhóm con, cuối cùng kết hợp các kết quả đã sắp xếp; cái gì đó như:

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 6

Bạn có thể sử dụng một comparer tùy chỉnh - báo cáo kết quả đặt hàng sau đó sẽ là:

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

nơi MyComparer được định nghĩa như thế này:

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

Mặc dù điều này có vẻ một bit tiết, nó đóng gói logic sắp xếp thành một loại thích hợp. Sau đó bạn có thể, nếu bạn muốn, dễ dàng chịu sự so sánh với kiểm tra tự động (kiểm tra đơn vị). Nó cũng có thể tái sử dụng được.

(Có thể để làm cho thuật toán rõ ràng hơn một chút, nhưng điều này là tốt nhất tôi có thể nhanh chóng ném nhau.)

Answer 7

Bạn cũng có thể "ăn gian" trong một nghĩa nào đó.Dựa trên mô tả của bạn về vấn đề này, bạn biết bất kỳ chuỗi độ dài 2 sẽ là một số. Vì vậy, chỉ cần sắp xếp tất cả các chuỗi chiều dài 1. Và sau đó sắp xếp tất cả các chuỗi chiều dài 2. Và sau đó làm một bó trao đổi để sắp xếp lại các chuỗi của bạn theo thứ tự đúng. Về cơ bản, quy trình sẽ hoạt động như sau: (giả sử dữ liệu của bạn nằm trong một mảng.)

Bước 1: Đẩy tất cả các chuỗi có độ dài 2 đến cuối mảng. Theo dõi số lượng bạn có.

Bước 2: Ở vị trí sắp xếp các Strings có độ dài 1 và Strings chiều dài 2.

Bước 3: tìm kiếm nhị phân cho 'a' đó sẽ là trên ranh giới của hai nửa của bạn.

Bước 4: Hoán đổi hai chữ số của bạn bằng các chữ cái nếu cần.

Điều đó nói rằng, trong khi cách tiếp cận này sẽ hoạt động, không liên quan đến cụm từ thông dụng và không cố gắng phân tích các giá trị không phải là int - Tôi không khuyến nghị. Bạn sẽ viết nhiều mã hơn các phương pháp khác đã được đề xuất. Nó làm xáo trộn quan điểm của những gì bạn đang cố gắng làm. Nó không hoạt động nếu bạn đột nhiên nhận được hai chữ cái Strings hoặc ba chữ số Strings. Vv Tôi chỉ bao gồm nó để cho thấy cách bạn có thể xem xét các vấn đề khác nhau và đưa ra các giải pháp thay thế.

Answer 8

Bạn chỉ có thể sử dụng chức năng provided by the Win32 API:

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

và gọi nó là từ một IComparer như những người khác đã chỉ ra.

Answer 9

Sử dụng Schwartzian Transform để thực hiện chuyển đổi 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

Tôi đã gặp sự cố tương tự và đã hạ cánh tại đây: phân loại các chuỗi có hậu tố dạng số như trong ví dụ sau.

gốc:

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

Mặc định loại kết quả:

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

kết quả loại mong muốn:

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

tôi đã kết thúc bằng một Comparer tùy chỉnh:

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)