代码之家 › 专栏 › 技术社区 › Toshi

方法,该方法识别IEnumerable是否已排序

sorting list c#

Toshi · 技术社区 · 6 年前

我有这个扩展方法来检查是否对任何类型的列表进行了排序

public static bool IsSorted<T>(this IEnumerable<T> input)
{
    IEnumerable<T> expectedListASC = input.OrderBy(x => x);
    IEnumerable<T> expectedListDESC = input.OrderByDescending(x => x);
    return expectedListASC.SequenceEqual(input) || expectedListDESC.SequenceEqual(input);
}

但如果是大名单,那就需要时间了。有没有更有效的方法得到同样的结果?

3 回复 | 直到 6 年前

Lasse V. Karlsen 6 年前

这里有一个泛型方法,它应该检测序列是按递增顺序还是递减顺序排列,然后检查集合的其余部分是否遵循顺序。

它有不经过全面测试,如果您决定使用它,您应该将数据集左右抛出并编写单元测试。

public static class CollectionExtensions
{
    public static bool IsOrdered<T>(this IEnumerable<T> collection, IComparer<T> comparer = null)
    {
        comparer = comparer ?? Comparer<T>.Default;

        bool? expectedToIncrease = null;
        using (var enumerator = collection.GetEnumerator())
        {
            bool gotFirst = enumerator.MoveNext();
            if (!gotFirst)
                return true; // empty collection is ordered
            var first = enumerator.Current;
            T second = default(T);

            while (expectedToIncrease is null)
            {
                bool gotSecond = enumerator.MoveNext();
                if (!gotSecond)
                    return true; // only equal elements are ordered
                second = enumerator.Current;

                switch (comparer.Compare(first, second))
                {
                    case int i when i < 0:
                        expectedToIncrease = false;
                        break;

                    case int i when i > 0:
                        expectedToIncrease = true;
                        break;
                }

                if (expectedToIncrease is null)
                    first = second; // prepare for next round
            }

            while (enumerator.MoveNext())
            {
                if (expectedToIncrease.GetValueOrDefault())
                {
                    if (comparer.Compare(second, enumerator.Current) < 0)
                        return false;
                }
                else
                {
                    if (comparer.Compare(second, enumerator.Current) > 0)
                        return false;
                }
            }

            return true;
        }
    }
}

ProgrammingLlama Raveena Sarda 6 年前

这样的事情应该管用:

public static bool IsSorted<T>(IEnumerable<T> input)
{
    if (input is IOrderedEnumerable<T>)
    {
        return true;
    }

    var comparer = Comparer<T>.Default;
    T previous = default(T);
    bool previousSet = false;
    bool? comparisonOrder = null;
    foreach (var value in input)
    {
        if (!previousSet)
        {
            previous = value;
            previousSet = true;
        }
        else
        {
            int comparisonResult = comparer.Compare(previous, value);
            if (comparisonResult != 0)
            {
                if (!comparisonOrder.HasValue)
                {
                    comparisonOrder = comparisonResult > 0;
                }
                else if (comparisonResult > 0 != comparisonOrder)
                {
                    return false;
                }
            }
            previous = value;
        }
    }
    return true;
}

它在跟踪上一个项目的同时遍历每个项目,然后使用默认比较器(如 .OrderBy() 会)检查它们是否分类。为了检查任意方向的排序,我存储第一个非零比较的结果,并将其用作检查点。

正如评论中已经指出的,并非所有 IEnumerable s是可重写的,并且根据提供 不可数 . 另外,考虑一下 不可数 它返回随机数-每次迭代时,它都会给出不同的值(假设每次的种子都不相同)。

对50000个项目(5000次迭代)的排序列表进行的测试表明:

Lasse用了2137毫秒来确定它是否被分类。
我的方法用了2348毫秒来确定 不可数 已排序。
MineR用了2403毫秒才返回结果。

MineR 6 年前

我提供了下面的解决方案,它只与其他解决方案不同,因为您可以指定比较器,它将告诉您集合的排序顺序。

public static class LinqHelpers
{
    [Flags]
    public enum SortDirections
    {
        NotSorted = 0,
        Ascending = 1,
        Descending = 2,
    }
    public static SortDirections GetSortDirection<T>(this IEnumerable<T> input, IComparer<T> comparer = null)
    {
        comparer = comparer ?? Comparer<T>.Default;

        bool isAsc = true;
        bool isDsc = true;
        bool isFirst = true;
        T last = default(T);
        foreach (var val in input)
        {
            if (isFirst)
            {
                isFirst = false;
            }
            else
            {
                int cmp = comparer.Compare(last, val);
                if (cmp > 0) isAsc = false;
                if (cmp < 0) isDsc = false;
            }
            if (!isAsc && !isDsc) break;
            last = val;
        }
        int result = 0;
        if (isAsc) result |= (int)SortDirections.Ascending;
        if (isDsc) result |= (int)SortDirections.Descending;
        return (SortDirections)result;
    }
}

一些边缘案例:

如果0个元素,则视为在两个方向上排序。
如果是1个元素,则认为它是双向排序的。
如果所有元素都相同,则视为在两个方向上排序。

为什么你对大数据集的处理速度慢?您正在对数据进行排序,即O(n logn)。这个问题只需要O(n)。