logo标签列表

优化一个 list<T>.Sort(Comparer)。

c#genericssortingcollections
3
我有一个列表，存储了一些整数。 我不喜欢默认的List.Sort()方法，因为我希望按实际整数大小对列表进行排序。 到目前为止，我有以下代码：
哦，这些整数是以字符串形式存储的，例如“1234”。这是我无法改变的。
public class IntComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        if (x == null)
        {
            if (y == null)
            {
                // If x is null and y is null, they're
                // equal. 
                return 0;
            }
            else
            {
                // If x is null and y is not null, y
                // is greater. 
                return -1;
            }
        }
        else
        {
            // If x is not null...
            //
            if (y == null)
            // ...and y is null, x is greater.
            {
                return 1;
            }
            else
            {
                // ...and y is not null, compare the 
                // lengths of the two strings.
                //
                int xInt = Convert.ToInt32(x);
                int yInt = Convert.ToInt32(y);

                if (x > y)
                {
                    // If the strings are not of equal length,
                    // the longer string is greater.
                    //
                    return 1;
                }
                else if (xInt == yInt)
                {
                    return 0;
                }
                else
                {
                    // If the strings are of equal length,
                    // sort them with ordinary string comparison.


        //
                return -1;
            }
        }
    }
}

据我所知，这是冒泡排序，对吗？我应该使用什么替代它呢？快速排序？而且，我可能需要帮助编写它。

哦，我的列表包含不到两千个元素，其中存储着字符串形式的数字。

另外，我这样调用我的 IComparer：

IntComparer intSort = New IntComparer();
List<T>.Sort(intSort);
6个回答
6
假设您想按存储为字符串的整数值进行排序，可以简单地执行以下操作：
numbers.Sort((x,y) => Int32.Parse(x).CompareTo(Int32.Parse(y)));
糟糕 - 几乎一模一样，但你比我快了3分钟。+1 ;-p - Marc Gravell
每件事情都有第一次 :) - Brian Rasmussen
你知道在与将自己的IComparer添加到List.Sort()相比，这个方法会不会更快/更慢/一样快吗？ 我不确定在这种情况下Linq有多快 :) - CasperT
这是一个比较器，它只是作为匿名方法实现。正如ammoQ的答案所指出的那样，排序算法和比较器是独立的实体。 - Brian Rasmussen
哦，好的，我不太确定他的回答意味着什么，所以我避免了它。这有点澄清了 :) - CasperT
4

您需要知道比较器和排序算法是相互独立的。因此，这个比较器可以与冒泡排序、快速排序、堆排序或任何其他排序算法一起使用。根据 MSDN，List.Sort 的内置排序算法是快速排序。

哦？但是如果我只调用List<T>.Sort()，我的列表根本不会按整数大小排序 - 而这正是我想要实现的。 - CasperT
啊，我现在有点明白了。所以当我的List.Sort调用这个比较器时，这意味着我正在执行快速排序，对吗？而不是冒泡排序，因为我最初的想法是由于我编写的比较器的方式。 - CasperT
1

所以你有一个由字符串表示整数的列表作为输入，并且你想要一个排序后的整数列表作为输出？

看起来你在这里做了很多工作，为了得到你想要的结果，你可以利用一些 Linq 来获得你的结果，像这样：

using System;

using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication6
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var unsortedListOfStringsAsInts = new List<string> {"1234", "2345", "7", "9"};
            var sortedListOfInts = unsortedListOfStringsAsInts.Select(x => int.Parse(x)).OrderBy(x => x).ToList();

            foreach (var i in sortedListOfInts)
                Console.WriteLine(i);
        }
    }
}

我不会担心手动优化你的排序算法，即使有两千个项目 - 除非这是你的应用程序正在做的“全部”，否则这并不是需要排序的太多项目。

只是似乎生成/创建一个全新的列表太浪费了 :) 不，这只是我的代码的一部分，但我想应该研究一下这个问题并变得更好 - 掌握排序是个好主意。我确实喜欢你的LINQ解决方案，我也会进一步研究它 - CasperT
是的，掌握排序是个好主意，毫无疑问 :) - Steve Willcock
1

不，对于排序列表使用的算法是QuickSort，因此您不能轻易地对其进行改进。

List<T>.Sort方法

该方法使用Array.Sort，它使用QuickSort算法。

我已完成比较器：

public class IntComparer : IComparer<string> {

    private static int ParseInt32(string text) {
        long value = 0;
        foreach (char c in text) {
                if (c >= '0' && c <= '9') {
                value = value * 10 + c - '0';
            } else {
                throw new FormatException();
            }
        }
        if (value > int.MaxValue) throw new OverflowException();
        return (int)value;
    }


    public int Compare(string x, string y) {
        if (x == null) {
            if (y == null) {
                // If x is null and y is null, they're
                // equal. 
                return 0;
            } else {
                // If x is null and y is not null, y
                // is greater. 
                return -1;
            }
        } else {
            // If x is not null...
            //
            if (y == null) {
                // ...and y is null, x is greater.
                return 1;
            } else {
                // ...and y is not null, compare the 
                // lengths of the two strings.
                //
                if (x.Length != y.Length) {
                    // If the strings are not of equal length,
                    // the longer string is greater.
                    return x.Length - y.Length;
                } else {
                    // compare numerically
                    int xInt = ParseInt32(x);
                    int yInt = ParseInt32(y);
                    return xInt - yInt;
                }
            }
        }
    }

}

编辑：
我添加了一个更快的整数解析器。由于比较器无法处理负值，解析器也不能处理，这使得进一步优化成为可能。

你知道这是否更快吗？:) 尽管如此，我确实喜欢它！+1 - CasperT
如果ParseInt32方法比Int32.Parse快？ 是的，它大约快十倍。 - Guffa
1

我认为你应该先将 string 转换为临时的 int 列表，因为其他代码在每次比较时都会重复地转换字符串（到目前为止）。如果保留 null 很重要，你也可以使用可空的 int。之后，对列表进行排序，必要时再转换回字符串。

字符串解析是性能瓶颈中最大的，所以+1。 - Jim Arnold
0

这里有一个快速示例，只要您使用的是 .net 3.5 项目（Linq）

using System.Linq;
using System.Collections.Generic;

List<string> unorderedList = List<string>();
list.Add("3");
list.Add("5");
list.Add("2");
list.Add("10");
list.Add("-6");
list.Add("7");

List<string> orderedList = list.OrderBy(x => int.Parse(x)).ToList();
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接