排序算法

Question

这是我的丑陋代码，需要对我的数据进行排序。我不太熟悉C#，因为我实际上是一个Java程序员。

如何在不影响性能的情况下重写此代码？我知道我需要反射，但这对我的表现很不利。

sortings是必须排序的字段的列表，如果必须是ASC和DESC的话。leistungen是要排序的数据。

课程：

public class Aufzeichnung
{
    public string Mitarbeiter { get; set; }
    public int Dauer { get; set; }
    public double Kosten { get; set; }
}

public class Leistung
{
    public int ID { get; set; }
    public string Art { get; set; }
    public string Angebot { get; set; }
    public string Jahr { get; set; }
    public string Berater { get; set; }
    public string Assistent { get; set; }
    public double Preis { get; set; }
    public List<Aufzeichnung> Aufzeichnungen { get; set; }
}

public class LaufendeLeistung
{
    public string Kunde { get; set; }
    public List<Leistung> Leistungen { get; set; }
}

算法：

internal static IEnumerable<A> Sort(List<A> leistungen, IEnumerable<Sorting> sortings)
    {
        for (int i = 0; i < sortings.Count(); i++)
        {
            var sort = sortings.ElementAt(i).Ascending ? 1 : -1;

            if (sortings.ElementAt(i).Field.Equals("Kunde"))
            {
                leistungen.Sort((a,b) => string.Compare(a.Kunde,b.Kunde)*sort);
            } 
            else 
            {
                for (var j = 0; j < leistungen.Count(); j++)
                {
                    if (sortings.ElementAt(i).Field.Equals("Leistung"))
                    {
                        leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Art, b.Art) * sort);
                    }
                    else if (sortings.ElementAt(i).Field.Equals("Angebot"))
                    {
                        leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Angebot, b.Angebot) * sort);
                    }
                    else if (sortings.ElementAt(i).Field.Equals("Jahr"))
                    {
                        leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Jahr, b.Jahr) * sort);
                    }
                    else if (sortings.ElementAt(i).Field.Equals("Berater"))
                    {
                        leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Berater, b.Berater) * sort);
                    }
                    else if (sortings.ElementAt(i).Field.Equals("Assistent"))
                    {
                        leistungen[j].Leistungen.Sort((a, b) => string.Compare(a.Assistent, b.Assistent) * sort);
                    }
                    else if (sortings.ElementAt(i).Field.Equals("Mitarbeiter"))
                    {
                        for (var k = 0; k < leistungen[j].Leistungen.Count(); k++)
                        {
                            if (leistungen[j].Leistungen[k].Aufzeichnungen != null)
                            {
                                leistungen[j].Leistungen[k].Aufzeichnungen.Sort((a, b) => string.Compare(a.Mitarbeiter, b.Mitarbeiter) * sort);
                            }
                        }

                    }

                }
            }
        }
        return leistungen;
    }

Answer 1

编辑

我最初的答案并不是动态地进行升序/降序排序。所以这是我的主意。注意，这与@ratchetFreak回答.不同，关键是IComparer<T>会自动重写对象的IComparable<T>实现。

1. 新类，LeistungComparer : Comparer<T>
   1. public abstract class Comparer<T> : IComparer<T> -所以继承和我们得到了接口。
   2. 我们将传递一个构造函数参数来判断排序的方式。

2. 将Leistung.CompareTo()代码移动到这个新类。
3. Leistung.CompareTo()只会打电话给LeistungComparer.Compare() -仅此而已！

上述实际操作：

// ***** default ascending sort
Leistung yourLeistung = new Leistung( );
Leistung yourLeistung2 = new Leistung( );
List<Leistung> yourList = new List<Leistung>();
yourList.Add(yourLeistung);
yourList.Add(yourLeistung2);
// stuff happens, then...
yourList.Sort();

// override
yourList.Sort( new LeistungComparer( SortOrder.descend ) );

详细信息

public enum SortOrder { undefined, ascend, descend }

public class LeistungComparer : Comparer<Leistung>
{
    protected int SortBy { get; set; }

    /// <summary>
    /// Default sort order is ascending
    /// </summary>
    /// <param name="sortOrder">defaults to ascend</param>
    public LeistungComparer( SortOrder sortOrder = SortOrder.ascend )
    {
        if ( sortOrder == SortOrder.ascend ) SortBy = 1;
        if ( sortOrder == SortOrder.descend ) SortBy = -1;
        if ( sortOrder == SortOrder.undefined )
            throw new NotImplementedException( "Sort Order is undefined" );
    }


    public override int Compare( Leistung x, Leistung y )
    {
        int result = SortBy;

        if ( x != null && y == null ) return result;
        if ( x == null && y != null ) return result * SortBy;
        if ( x == null && y == null ) return 0;

        result = x.Art.CompareTo( y.Art ) * SortBy;

        if ( result == 0 )
            result = CompareAngebot( x, y );

        return result * SortBy;
    }

    protected int CompareAngebot( Leistung x, Leistung y )
    {
        int result = SortBy;
        result = x.Angebot.CompareTo( y.Angebot ) * SortBy;

        if ( result == 0 )
            result = CompareJahr( x, y );

        return result;
    }

    protected int CompareJahr( Leistung x, Leistung y )
    {
        // you get the idea

        return 1;
    }
}


public class Leistung : IComparable<Leistung>
{
    // properties removed for readability

    protected LeistungComparer Comparer { get; set; }

    public Leistung (LeistungComparer comparer = null){
        Comparer = comparer ?? new LeistungComparer();
    }

    public int CompareTo( Leistung other )
    {
        return Comparer.Compare( this, other );
    }
}

端编辑

注:原答案如下。它没有被修改过。

启用排序的惯用方法是实现IComparable接口。这肯定会简化排序代码。所以：

public class Leistungen : IComparable<Leistungen> {  }
public class Aufzeichnung : IComparable<Aufzeichnung> { }

然后你就可以这样分类：

List<Leistungen> myLeistungen;  // pretend we instantiated it too.

myLeistungen.Sort();

如果您想要不同的排序算法，那么为每个算法创建一个IComparer类，就像@ratchet是的所建议的那样。然后您可以执行以下操作--这将覆盖类IComparalble中的Leistungen实现：

myLeistungen.Sort(myDifferentComparer);

IComparable实现

这演示了如何比较多个属性。您的两个类都将使用此模式实现。当Leistungen.CompareTo()开始比较它的List<Aufzeichnung>时，好的Aufzeichnung.CompareTo()会处理这个问题！

public class Leistungen : IComparable<Leistungen> {
    \\ implementing the generic version means we don't 
    \\ check for or cast to the correct type.
    public int CompareTo(Leistungen other) {
        int result = 1; // "this" is > "other"

        if(other == null) return result;

        result = this.Art.CompareTo(other.Art);

        if(result == 0)
            result = CompareAngebot(other);

        return result;
    }

    protected int CompareAngebot(Leistungen other) {
        int result = 1;
        result = this.Angebot.CompareTo(other.Angebot);

        if(result == 0)
           result = CompareJahr(other);

        return result;
    }

    protected int CompareJahr(Leistungen other) { // you get the idea }

    // ....

    protected int CompareAufzeichnungList(Leistungen other) {
        // last property in our compare chain, so it's real simple

        return this.Aufzeichnungen.CompareTo(other.Aufzeichnungen);
    }

}

Answer 2

我认为，即使不完全重写代码，也有一些优化的潜力。

1. 通过一次又一次地使用sortings.ElementAt(i)，实际上每次都会得到可枚举元素。到目前为止，我认为没有理由不使用foreach (var sorting in sortings)和在循环中使用sorting变量，而不是for循环。
2. 根据通过Sort参数传递给sortings方法的数量和排序字段，您可能会一次又一次地重新排序相同的列表(S)。由于List.Sort实际上每次都对数组进行重新排序，这是不可忽略的。
3. 有一种情况需要对leistungen列表本身进行排序，另一种情况是需要排序Aufzeichnungen列表。您可以在迭代所有内容之前识别它们(只需使用与字段名匹配的sortings列表的最后一个条目来获得正确的排序顺序)，然后从循环中分别应用它们。

从外部的角度来看，leistungen列表在适当的位置排序，然后作为IEnumerable<A>返回，这也可能是意外的。我至少要添加一些文档，说明输入列表将被修改。

您的一个巨大缺点可能是，您依赖于调用Array.Sort来实现多个级别的排序。我的建议是尝试使用内置的LINQ方法。通过链接OrderBy/ThenBy调用，可以避免多次运行排序算法，而是使用LINQ的延迟执行。这里有一个关于它如何工作的建议：

public static class Sorter<A> where A : LaufendeLeistung
{
    private static readonly IReadOnlyDictionary<string, Func<Leistung, string>> leistungKeySelectors;

    static Sorter()
    {
        var selectors = new Dictionary<string, Func<Leistung, string>>();

        selectors.Add("Leistung", l => l.Art);
        selectors.Add("Angebot", l => l.Angebot);
        selectors.Add("Jahr", l => l.Jahr);
        selectors.Add("Berater", l => l.Berater);
        selectors.Add("Assistent", l => l.Assistent);

        leistungKeySelectors = selectors;
    }

    internal static IEnumerable<A> Sort(List<A> leistungen, IEnumerable<Sorting> sortings)
    {
        if (leistungen == null)
        {
            throw new ArgumentNullException(nameof(leistungen));
        }

        return sortings == null ? leistungen : SortImpl(leistungen, sortings);
    }

    private static IEnumerable<A> SortImpl(IEnumerable<A> leistungen, IEnumerable<Sorting> sortings)
    {
        var customerSorting = sortings.LastOrDefault(s => "Kunde".Equals(s.Field, StringComparison.Ordinal));
        var employeeSorting = sortings.LastOrDefault(s => "Mitarbeiter".Equals(s.Field, StringComparison.Ordinal));

        if (customerSorting != null)
        {
            leistungen = leistungen.OrderBy(k => k.Kunde, customerSorting);
        }

        var leistungenSortings = sortings.Where(s => !"Kunde".Equals(s.Field, StringComparison.Ordinal) && !"Mitarbeiter".Equals(s.Field, StringComparison.Ordinal)).ToList();

        foreach (var laufendeLeistung in leistungen)
        {
            if (laufendeLeistung.Leistungen != null)
            {
                laufendeLeistung.Leistungen = ProcessLeistungen(laufendeLeistung.Leistungen, leistungenSortings, employeeSorting).ToList();
            }

            yield return laufendeLeistung;
        }
    }

    private static IEnumerable<Leistung> ProcessLeistungen(IEnumerable<Leistung> leistungen, IEnumerable<Sorting> sortings, Sorting employeeSorting)
    {
        foreach (var leistung in SortLeistungenByProperties(leistungen, sortings))
        {
            if (employeeSorting != null && leistung.Aufzeichnungen != null)
            {
                leistung.Aufzeichnungen = leistung.Aufzeichnungen.OrderBy(a => a.Mitarbeiter, employeeSorting).ToList();
            }

            yield return leistung;
        }
    }

    private static IEnumerable<Leistung> SortLeistungenByProperties(IEnumerable<Leistung> leistungen, IEnumerable<Sorting> sortings)
    {
        foreach (var sorting in sortings)
        {
            // Just an alternative to the switch/case statement.
            Func<Leistung, string> selector;
            if (leistungKeySelectors.TryGetValue(sorting.Field, out selector))
            {
                leistungen = leistungen.OrderBy(selector, sorting);
            }
        }

        return leistungen;
    }
}

public static class ExtensionMethods
{
    public static IOrderedEnumerable<T> OrderBy<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector, Sorting sorting)
    {
        var result = source as IOrderedEnumerable<T>;
        if (result != null)
        {

            result = sorting.Ascending ? result.ThenBy(keySelector) : result.ThenByDescending(keySelector);
        }
        else
        {
            result = sorting.Ascending ? source.OrderBy(keySelector) : source.OrderByDescending(keySelector);
        }

        return result;
    }
}

请注意，这假设实际上不需要对List<LaufendeLeistung>进行排序，也不应该有任何使用者依赖于Leistungen或Aufzeichnungen不被替换(毕竟有一个公共设置程序)。由于某些分配(枚举数、字典、列表)，内存使用率可能会略高一些，但使用几个sortings可能会更快，因为没有对支持列表的数组进行实际排序。(如果这很重要，就用基准来衡量。：)

Answer 3

您可以定义一个包含多个IComparer的IComparers，并返回不是0的第一个结果：

class CascadedComparer<T> : IComparer<T>{

    IList<IComparer<T>> comparings; //fill in constructor

    public int Compare(T x, T y){
        foreach(var comp in comparings){
            int r = comp.compare(x, y);

            if(r!=0) 
                return r;
        }
        return 0; //all returned 0
    }

}

然后，您可以将一个用特定字段比较器填充的实例传递给sort方法leistungen[j].Leistungen。

Sorting不需要保存字段的字符串值来进行比较，而是需要保存比较器(或映射函数)。

或者，您可以构建一个map<string, IComparer<A>>，然后您可以直接从地图中得到比较器。