logo标签列表

C#排序数组（升序和降序）

c#arrayssorting
8

我遇到了一个问题，需要编写一个方法，如果数组（数字）的元素按升序或降序排列，则返回true，否则返回false。如果数组是按升序排列的，我可以返回正确的布尔值，但我不知道如何在同一个方法中检查降序排列。我目前有：

public static bool IsArraySorted(int[] numbers)
{
    for (int i = 1; i < numbers.Length; i++)
    {
        if (numbers[i - 1] > numbers[i])
            return false;
    }

    return true;
}

有没有人能够帮忙检查一个按降序排列的数组呢？谢谢！

如果有两个连续的值具有相同的数字，这是期望的行为吗？ - Marc Cals
使用return会退出函数，而你可能想在返回任何内容之前循环整个集合... - Laurent S.
@Bartdude 我认为这是设计上的 - 如果你已经发现它没有排序，那么就没有必要检查数组的其余部分了 :-) - Lars Kristensen
8个回答
9
应该是这样的：

这应该类似于：

public static bool IsArraySorted(int[] numbers)
{
    bool? ascending = null;

    for (int i = 1; i < numbers.Length; i++)
    {
        if (numbers[i - 1] != numbers[i])
        {
            bool ascending2 = numbers[i - 1] < numbers[i];

            if (ascending == null)
            {
                ascending = ascending2;
            }
            else if (ascending.Value != ascending2)
            {
                return false;
            }
        }
    }

    return true;
}

请注意使用ascending变量来保存数组的“方向”。它在第一次找到两个不同的元素时被初始化。
请注意，如果您想，甚至可以返回数组的“方向”：
public static bool IsArraySorted(int[] numbers, out bool isAscending)
{
    isAscending = true;
    bool? ascending = null;

在 if (ascending == null) 语句的内部

if (ascending == null)
{
    ascending = ascending2;
    isAscending = ascending2;
}

这是一个基于 IEnumerable<TSource> 的通用版本：

public static bool IsSorted<TSource>(IEnumerable<TSource> source, out bool isAscending, Comparer<TSource> comparer = null)
{
    isAscending = true;

    if (comparer == null)
    {
        comparer = Comparer<TSource>.Default;
    }

    bool first = true;
    TSource previous = default(TSource);

    bool? ascending = null;

    foreach (TSource current in source)
    {
        if (!first)
        {
            int cmp = comparer.Compare(previous, current);

            if (cmp != 0)
            {
                bool ascending2 = cmp < 0;

                if (ascending == null)
                {
                    ascending = ascending2;
                    isAscending = ascending2;
                }
                else if (ascending.Value != ascending2)
                {
                    return false;
                }
            }
        }

        first = false;
        previous = current;
    }

    return true;
}

请注意使用bool first/TSource previous来处理i - 1（以及for循环能够“跳过”第一个元素的事实）。
我能否只使用(numbers.Length/2)而不必遍历整个列表？ - Amit
2
@Amit 你好，如果不检查最后一个值，你该如何捕捉到顺序错误的-5呢？数组为{1, 2, 3, -5}。 - xanatos
@xanatos，如果传入的数组长度为0或1，则会出现“OutOfRangeException”。您需要在方法顶部进行一些参数检查。 - Wyatt Earp
@WyattEarp 不会...因为在for()之前没有访问数组的代码，而且对于长度小于等于1的数组，for()将会被阻塞，int i = 1; i < numbers.Length。 - xanatos
@xanatos，啊，我的错误。不过，如果数组为空，你会得到一个“NullReferenceException”。 - Wyatt Earp
@WyattEarp 是的，原始代码中没有检查，我试图保持代码“原样”。 - xanatos
3

Using Linq - 

public static bool IsArraySorted(int[] numbers)
{
    var orderedAsc = numbers.OrderBy(a => a);
    var orderedDes = numbers.OrderByDescending(a => a);

    bool isSorted = numbers.SequenceEqual(orderedAsc) ||
                    numbers.SequenceEqual(orderedDes);
    return isSorted;
}
2

这个使用一个循环来测试两种情况：

public static bool IsSorted<T>(IEnumerable<T> items, Comparer<T> comparer = null)
{
    if (items == null) throw new ArgumentNullException("items");
    if (!items.Skip(1).Any()) return true;  // only one item

    if (comparer == null) comparer = Comparer<T>.Default;
    bool ascendingOrder = true; bool descendingOrder = true;

    T last = items.First();
    foreach (T current in items.Skip(1))
    {
        int diff = comparer.Compare(last, current);
        if (diff > 0)
        {
            ascendingOrder = false;
        }
        if (diff < 0)
        {
            descendingOrder = false;
        }
        last = current;
        if(!ascendingOrder && !descendingOrder) return false;
    }
    return (ascendingOrder || descendingOrder);
}

使用方法：

int[] ints = { 1, 2, 3, 4, 5, 6 };
bool isOrderedAsc = IsSorted(ints); // true
bool isOrderedDesc = IsSorted(ints.Reverse()); //true

如果你将它作为扩展方法，你可以在任何类型中使用它：

bool ordered = new[]{"A", "B", "C"}.IsSorted();
1
我认为两次枚举 IEnumerable<> 是一件非常糟糕的事情，这是非常不好的。（First/Skip） - xanatos
@xanatos：为什么？我不会两次枚举它。如果它是一个集合，那么只需取第一个项目，而Skip(1)则是省略第一个的枚举。哪里出了问题？ - Tim Schmelter
1
尝试对 IQueryable<> 进行操作... 查询会被解析两次（实际上会执行两个不同的查询... 一个带有 TOP 1，另一个模拟了 Skip(1)）。 - xanatos
@xanatos：你为什么想要使用这种方法进行数据库查询？虽然你可以这样做，但它并不是为此目的而设计的。另一方面，你的方法根本不可重用。他可以更改签名以仅接受 IList<T>，但我不会这样做。 - Tim Schmelter
你的代码/解释中是否明确表示“我将枚举两次，请勿在使用缓慢的IEnumerable<>时使用我”？警告标签非常重要。 - xanatos
@xanatos：怎么了？如果你对除int以外的任何类型和数组之外的任何集合类型都不关心，为什么你会对这个如此在意呢？如果它是一个int[]，我的回答并没有明显地变得不够高效，所以我看不出问题所在。 - Tim Schmelter
1
public static boolean checkSortedness(final int[] data) 
{
    for (int i = 1; i < data.length; i++) 
    {
        if (data[i-1] > data[i]) {
            return false;
        }
    }
    return true;
}
这只验证升序排序的列表，但在降序排序的列表上失败。 - fubo
final is Java, not C# - xanatos
1

我的答案在哪里？我大约一个小时前写的：

public enum SortType
{
     unsorted   = 0,
     ascending  = 1,
     descending = 2
}

public static SortType IsArraySorted(int[] numbers)
{
    bool ascSorted = true;
    bool descSorted = true;

    List<int> asc = new List<int>(numbers);            

    asc.Sort();

    for (int i = 0; i < asc.Count; i++)
    {
        if (numbers[i] != asc[i]) ascSorted = false;
        if (numbers[asc.Count - 1 - i] != asc[i]) descSorted = false;
    }

    return ascSorted ? SortType.ascending : (descSorted? SortType.descending : SortType.unsorted);
}

例子：

enter image description here

0
我编写了这个方法来检查一个数组是否按升序排序。感谢您的评论。

        static void Main(string[] args)
        {
            int[] arrayToCheck = { 1, 1, 3, 5 ,2, 7};
            
            Console.WriteLine(IsSorted(arrayToCheck));
            
        }

在第一步中，我设置了“for循环”，以检查每个单独的数组整数是否小于索引为-1的整数。然后，我创建了一个布尔数组，存储了所有这些条件（真/假）。
 static bool IsSorted(int[] array)
        {
            bool[] checkAscending = new bool[array.Length - 1];

            for (int i = 1; i < array.Length; i++)
            {
                checkAscending[i - 1] = array[i] >= array[i - 1];
                
            }

在第二步中，为了将值1赋给true和0赋给false条件，我设置了“for loop”嵌套if和else条件。
            int[] trueToOne = new int[checkAscending.Length];
            
            for (int i = 0; i < checkAscending.Length; i++)
            {
                if (checkAscending[i] == true)
                    trueToOne[i] = 1;
                else if (checkAscending[i] == false)
                    trueToOne[i] = 0;
            }

在最后一步中，我必须创建一个新的方法“Add”，它以整数数组作为参数，并添加每个单独的数组字符。如果加法的结果等于数组trueToOne的长度，那么所有条件都为真，整数数组已排序。


            int result = Add(trueToOne);

            if (result == trueToOne.Length)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

并添加方法：


        public static int Add(int[] array)
        {
            int[] sum = new int[array.Length];


            for (int i = 1; i < array.Length; i++)
            {
                sum[0] = array[0];
                sum[i] = array[i] + sum[i - 1];
            }

            return sum[sum.Length - 1];
        }

    }
0

这更像是一个学术任务而不是实际问题。我猜偶尔回归基础也无妨：

public static bool IsSortedAscOrDesc(int[] arr)
{
    int last = arr.Length - 1;
    if (last < 1) return true;

    bool isSortedAsc = true;
    bool isSortedDesc = true;

    int i = 0;
    while (i < last && (isSortedAsc || isSortedDesc)) 
    {
        isSortedAsc &= (arr[i] <= arr[i + 1]);
        isSortedDesc &= (arr[i] >= arr[i + 1]);
        i++;
    }

    return isSortedAsc || isSortedDesc;
}
0

一个包含2个或更少元素的数组是有序的，
{0,0} 升序和降序都是有序的，{0,1} 升序，{1,0} 降序，{1,1} 升序和降序都是有序的。
可以使用一个循环，但将情况分开似乎更快。 对于一个包含超过2个元素的数组，
如果第一个元素小于最后一个元素， 检查：a[i] <= a[i + 1]。
下面我使用“ai <= (ai = a[i])”比较ai的旧值和新值，每个元素只读取一次。

using System;
class Program
{
    static void Main()
    {
        int i = 512; int[] a = new int[i--]; while (i > 0) a[i] = i--; //a[511] = 1;
        Console.WriteLine(isSorted0(a));
        var w = System.Diagnostics.Stopwatch.StartNew();
        for (i = 1000000; i > 0; i--) isSorted0(a);
        Console.Write(w.ElapsedMilliseconds); Console.Read();
    }

    static bool isSorted0(int[] a)  // 267 ms
    {
        if (a.Length < 3) return true; int j = a.Length - 1;
        return a[0] < a[j] ? incr(a) : a[0] > a[j] ? decr(a) : same(a);
    }
    static bool incr(int[] a)
    {
        int ai = a[0], i = 1, j = a.Length;
        while (i < j && ai <= (ai = a[i])) i++; return i == j;
    }
    static bool decr(int[] a)
    {
        int ai = a[0], i = 1, j = a.Length;
        while (i < j && ai >= (ai = a[i])) i++; return i == j;
    }
    static bool same(int[] a)
    {
        int ai = a[0], i = 1, j = a.Length - 1;
        while (i < j && ai == a[i]) i++; return i == j;
    }

    static bool isSorted1(int[] numbers)  // 912 ms  accepted answer
    {
        bool? ascending = null;
        for (int i = 1; i < numbers.Length; i++)
            if (numbers[i - 1] != numbers[i])
            {
                bool ascending2 = numbers[i - 1] < numbers[i];
                if (ascending == null) ascending = ascending2;
                else if (ascending.Value != ascending2) return false;
            }
        return true;
    }
}

一段简短的版本。
    static bool isSorted(int[] a)
    {
        if (a.Length < 3) return true; int i = a.Length - 1, ai = a[i--];
        if (ai > a[0]) while (i >= 0 && ai >= (ai = a[i])) i--;
        else if (ai < a[0]) while (i >= 0 && ai <= (ai = a[i])) i--;
        else while (i >= 0 && ai == a[i]) i--; return i < 0;
    }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接