代码之家  ›  专栏  ›  技术社区  ›  Thorin Oakenshield

C中的排序列表<String>#

  •  16
  • Thorin Oakenshield  · 技术社区  · 14 年前

    如何根据项目的整数值对列表排序

    "1"
    "5"
    "3"
    "6"
    "11"
    "9"
    "NUM1"
    "NUM0"
    

    结果应该是

    "1"
    "3"
    "5"
    "6"
    "9"
    "11"
    "NUM0"
    "NUM1"
    

    有没有办法用LINQ或Lambda表达式来实现这一点?

    提前谢谢

    7 回复  |  直到 14 年前
        1
  •  16
  •   Marc Gravell    14 年前

    怎么样:

        list.Sort((x, y) =>
        {
            int ix, iy;
            return int.TryParse(x, out ix) && int.TryParse(y, out iy)
                  ? ix.CompareTo(iy) : string.Compare(x, y);
        });
    
        2
  •  16
  •   Lasse V. Karlsen    14 年前

    下面是一个幼稚的实现(从某种意义上说,它可能有很多unicode问题),它似乎做到了这一点:

    您可以将下面的代码复制到 LINQPad

    基本上,比较算法将识别字符串中的数字,并用前导零填充最短的数字,例如两个字符串 "Test123Abc" "Test7X" “测试123ABC” "Test007X" ,它应该产生你想要的。

    然而,当我说“幼稚”的时候,我的意思是这里可能有很多真正的unicode问题,比如处理音调符号和多码点字符。如果有人能给一个更好的实施,我很乐意看到它。

    笔记:

    • 这个实现实际上并不解析数字,所以任意长的数字应该可以正常工作

    代码:

    void Main()
    {
        List<string> input = new List<string>
        {
            "1", "5", "3", "6", "11", "9", "A1", "A0"
        };
        var output = input.NaturalSort();
        output.Dump();
    }
    
    public static class Extensions
    {
        public static IEnumerable<string> NaturalSort(
            this IEnumerable<string> collection)
        {
            return NaturalSort(collection, CultureInfo.CurrentCulture);
        }
    
        public static IEnumerable<string> NaturalSort(
            this IEnumerable<string> collection, CultureInfo cultureInfo)
        {
            return collection.OrderBy(s => s, new NaturalComparer(cultureInfo));
        }
    
        private class NaturalComparer : IComparer<string>
        {
            private readonly CultureInfo _CultureInfo;
    
            public NaturalComparer(CultureInfo cultureInfo)
            {
                _CultureInfo = cultureInfo;
            }
    
            public int Compare(string x, string y)
            {
                // simple cases
                if (x == y) // also handles null
                    return 0;
                if (x == null)
                    return -1;
                if (y == null)
                    return +1;
    
                int ix = 0;
                int iy = 0;
                while (ix < x.Length && iy < y.Length)
                {
                    if (Char.IsDigit(x[ix]) && Char.IsDigit(y[iy]))
                    {
                        // We found numbers, so grab both numbers
                        int ix1 = ix++;
                        int iy1 = iy++;
                        while (ix < x.Length && Char.IsDigit(x[ix]))
                            ix++;
                        while (iy < y.Length && Char.IsDigit(y[iy]))
                            iy++;
                        string numberFromX = x.Substring(ix1, ix - ix1);
                        string numberFromY = y.Substring(iy1, iy - iy1);
    
                        // Pad them with 0's to have the same length
                        int maxLength = Math.Max(
                            numberFromX.Length,
                            numberFromY.Length);
                        numberFromX = numberFromX.PadLeft(maxLength, '0');
                        numberFromY = numberFromY.PadLeft(maxLength, '0');
    
                        int comparison = _CultureInfo
                            .CompareInfo.Compare(numberFromX, numberFromY);
                        if (comparison != 0)
                            return comparison;
                    }
                    else
                    {
                        int comparison = _CultureInfo
                            .CompareInfo.Compare(x, ix, 1, y, iy, 1);
                        if (comparison != 0)
                            return comparison;
                        ix++;
                        iy++;
                    }
                }
    
                // we should not be here with no parts left, they're equal
                Debug.Assert(ix < x.Length || iy < y.Length);
    
                // we still got parts of x left, y comes first
                if (ix < x.Length)
                    return +1;
    
                // we still got parts of y left, x comes first
                return -1;
            }
        }
    }
    
        3
  •  2
  •   Kobi    14 年前

    public class NameAndNumber
    {
        public NameAndNumber(string s)
        {
            OriginalString = s;
            Match match = Regex.Match(s,@"^(.*?)(\d*)$");
            Name = match.Groups[1].Value;
            int number;
            int.TryParse(match.Groups[2].Value, out number);
            Number = number; //will get default value when blank
        }
    
        public string OriginalString { get; private set; }
        public string Name { get; private set; }
        public int Number { get; private set; }
    }
    

    现在编写比较器或手动排序变得很容易:

    var list = new List<string> { "ABC", "1", "5", "NUM44", "3", 
                                  "6", "11", "9", "NUM1", "NUM0" };
    
    var sorted = list.Select(str => new NameAndNumber(str))
        .OrderBy(n => n.Name)
        .ThenBy(n => n.Number);
    

    给出结果:

    1、3、5、6、9、11、ABC、NUM0、NUM1、NUM44

        4
  •  2
  •   Oliver    7 年前

    blog post 关于自然排序,他链接到所需算法的一些可用实现。

    其中一个链接指向 Dave Koelle C# implementation

    /*
     * The Alphanum Algorithm is an improved sorting algorithm for strings
     * containing numbers.  Instead of sorting numbers in ASCII order like
     * a standard sort, this algorithm sorts numbers in numeric order.
     *
     * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
     *
     * Based on the Java implementation of Dave Koelle's Alphanum algorithm.
     * Contributed by Jonathan Ruckwood <jonathan.ruckwood@gmail.com>
     *
     * Adapted by Dominik Hurnaus <dominik.hurnaus@gmail.com> to
     *   - correctly sort words where one word starts with another word
     *   - have slightly better performance
     *
     * Released under the MIT License - https://opensource.org/licenses/MIT
     *
     * Permission is hereby granted, free of charge, to any person obtaining
     * a copy of this software and associated documentation files (the "Software"),
     * to deal in the Software without restriction, including without limitation
     * the rights to use, copy, modify, merge, publish, distribute, sublicense,
     * and/or sell copies of the Software, and to permit persons to whom the
     * Software is furnished to do so, subject to the following conditions:
     *
     * The above copyright notice and this permission notice shall be included
     * in all copies or substantial portions of the Software.
     *
     * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
     * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
     * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
     * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
     * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
     * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
     * USE OR OTHER DEALINGS IN THE SOFTWARE.
     *
     */
    using System;
    using System.Collections;
    using System.Text;
    
    /*
     * Please compare against the latest Java version at http://www.DaveKoelle.com
     * to see the most recent modifications
     */
    namespace AlphanumComparator
    {
        public class AlphanumComparator : IComparer
        {
            private enum ChunkType {Alphanumeric, Numeric};
            private bool InChunk(char ch, char otherCh)
            {
                ChunkType type = ChunkType.Alphanumeric;
    
                if (char.IsDigit(otherCh))
                {
                    type = ChunkType.Numeric;
                }
    
                if ((type == ChunkType.Alphanumeric && char.IsDigit(ch))
                    || (type == ChunkType.Numeric && !char.IsDigit(ch)))
                {
                    return false;
                }
    
                return true;
            }
    
            public int Compare(object x, object y)
            {
                String s1 = x as string;
                String s2 = y as string;
                if (s1 == null || s2 == null)
                {
                    return 0;
                }
    
                int thisMarker = 0, thisNumericChunk = 0;
                int thatMarker = 0, thatNumericChunk = 0;
    
                while ((thisMarker < s1.Length) || (thatMarker < s2.Length))
                {
                    if (thisMarker >= s1.Length)
                    {
                        return -1;
                    }
                    else if (thatMarker >= s2.Length)
                    {
                        return 1;
                    }
                    char thisCh = s1[thisMarker];
                    char thatCh = s2[thatMarker];
    
                    StringBuilder thisChunk = new StringBuilder();
                    StringBuilder thatChunk = new StringBuilder();
    
                    while ((thisMarker < s1.Length) && (thisChunk.Length==0 ||InChunk(thisCh, thisChunk[0])))
                    {
                        thisChunk.Append(thisCh);
                        thisMarker++;
    
                        if (thisMarker < s1.Length)
                        {
                            thisCh = s1[thisMarker];
                        }
                    }
    
                    while ((thatMarker < s2.Length) && (thatChunk.Length==0 ||InChunk(thatCh, thatChunk[0])))
                    {
                        thatChunk.Append(thatCh);
                        thatMarker++;
    
                        if (thatMarker < s2.Length)
                        {
                            thatCh = s2[thatMarker];
                        }
                    }
    
                    int result = 0;
                    // If both chunks contain numeric characters, sort them numerically
                    if (char.IsDigit(thisChunk[0]) && char.IsDigit(thatChunk[0]))
                    {
                        thisNumericChunk = Convert.ToInt32(thisChunk.ToString());
                        thatNumericChunk = Convert.ToInt32(thatChunk.ToString());
    
                        if (thisNumericChunk < thatNumericChunk)
                        {
                            result = -1;
                        }
    
                        if (thisNumericChunk > thatNumericChunk)
                        {
                            result = 1;
                        }
                    }
                    else
                    {
                        result = thisChunk.ToString().CompareTo(thatChunk.ToString());
                    }
    
                    if (result != 0)
                    {
                        return result;
                    }
                }
    
                return 0;
            }
        }
    }
    
        5
  •  0
  •   asaf    8 年前

    这是最快的算法-花了我2 mili排序50个项目 ~

    static void Sort()
    {
        string[] partNumbers = new string[] {"A1", "A2", "A10", "A111"};
        string[] result = partNumbers.OrderBy(x => PadNumbers(x)).ToArray();
    }
    
    
    public static string PadNumbers(string input)
    {
            const int MAX_NUMBER_LEN = 10;
    
            string newInput = "";
            string currentNumber = "";
            foreach (char a in input)
            {
                if (!char.IsNumber(a))
                {
                    if (currentNumber == "")
                    {
                        newInput += a;
                        continue;
                    }
                    newInput += "0000000000000".Substring(0, MAX_NUMBER_LEN - currentNumber.Length) + currentNumber;
                    currentNumber = "";
                }
                currentNumber += a;
            }
            if (currentNumber != "")
            {
                newInput += "0000000000000".Substring(0, MAX_NUMBER_LEN - currentNumber.Length) + currentNumber;
            }
    
            return newInput;
        }
    

    ~

        6
  •  -1
  •   eugeneK    14 年前

    除此之外,我觉得你什么都不需要listName.排序(),因为sort()方法使用默认比较器对节点进行快速排序。默认比较器做的正是您感兴趣的事情。

        7
  •  -1
  •   Daan    7 年前

        var numericList = a.Where(i => int.TryParse(i, out _)).OrderBy(j => int.Parse(j)).ToList();
        var nonNumericList = a.Where(i => !int.TryParse(i, out _)).OrderBy(j => j).ToList();
        a.Clear();
        a.AddRange(numericList);
        a.AddRange(nonNumericList);