检查数组是否排序的最快方法
考虑到从一个非常大的函数返回的数组。
如果对数组进行排序，测试的fastest方法是什么？
最简单的方法是：
/// /// Determines if int array is sorted from 0 -> Max /// public static bool IsSorted(int[] arr) { for (int i = 1; i arr[i]) { return false; } } return true; }
您必须访问数组的每个元素以查看是否有任何未排序的内容。
你的O（n）方法速度和它一样快，没有任何关于数组可能状态的特殊知识。
您的代码专门测试数组是否在较低索引处使用较小值进行排序。 如果这不是您想要的，那么您的if会变得稍微复杂一些。 您的代码评论确实表明您正在追求的目标。
如果您对可能状态有特殊了解（比如，您知道它通常已经排序，但可能会将新数据添加到最后），您可以优化访问数组元素的顺序，以便在测试时更快地失败。数组未排序。
您可以利用硬件体系结构的知识通过对数组进行分区来并行检查数组的多个部分，首先比较分区的边界（快速检查失败），然后在单独的线程上为每个核心运行一个数组分区（不超过每个CPU核心1个线程）。 请注意，如果数组分区远小于高速缓存行的大小，则线程将倾向于相互竞争以访问包含该数组的内存。 multithreading只对相当大的数组非常有效。
更快的方法，平台目标：任何CPU，首选32位。
一个包含512个元素的排序数组：快〜25％。
static bool isSorted(int[] a) { int j = a.Length - 1; if (j < 1) return true; int ai = a[0], i = 1; while (i <= j && ai <= (ai = a[i])) i++; return i > j; }
目标：x64，相同的arrays：快〜40％。
static bool isSorted(int[] a) { int i = a.Length - 1; if (i <= 0) return true; if ((i & 1) > 0) { if (a[i] < a[i - 1]) return false; i--; } for (int ai = a[i]; i > 0; i -= 2) if (ai < (ai = a[i - 1]) || ai < (ai = a[i - 2])) return false; return a[0] <= a[1]; }
忘了一个，比我的第一个代码块慢一点。
static bool isSorted(int[] a) { int i = a.Length - 1; if (i < 1) return true; int ai = a[i--]; while (i >= 0 && ai >= (ai = a[i])) i--; return i < 0; }
测量它（见greybeard的评论）。
using System; // ????????? DEBUG ????????? using sw = System.Diagnostics.Stopwatch; // static bool abc() class Program // { // a <= b <= c ? { // int a=4,b=7,c=9; static void Main() // int i = 1; { // if (a <= (a = b)) //abc(); // { int i = 512; // i++; int[] a = new int[i--]; // if (a <= (a = c)) while (i > 0) a[i] = i--; // { sw sw = sw.StartNew(); // i++; for (i = 10000000; i > 0; i--) // } isSorted(a); // } sw.Stop(); // return i > 2; Console.Write(sw.ElapsedMilliseconds); // } Console.Read(); // static bool ABC(); } // { // int[]a={4,7,9}; static bool isSorted(int[] a) // OP Cannon // int i=1,j=2,ai=a[0]; { // L0: if(i<=j) for (int i = 1; i < a.Length; i++) // if(ai<=(ai=a[i])) if (a[i - 1] > a[i]) return false; // {i++;goto L0;} return true; // return i > j; } // } }
目标：x64。 四个核心/线程。 一个包含100,000个元素的排序数组：~55％。
static readonly object _locker = new object(); static bool isSorted(int[] a) // a.Length > 3 { bool b = true; Parallel.For(0, 4, k => { int i = 0, j = a.Length, ai = 0; if (k == 0) { j /= 4; ai = a[0]; } // 0 1 if (k == 1) { j /= 2; i = j / 2; ai = a[i]; } // 1 2 if (k == 2) { i = j - 1; ai = a[i]; j = j / 2 + j / 4; } // 4 3 if (k == 3) { i = j - j / 4; ai = a[i]; j = j / 2; } // 3 2 if (k < 2) while (b && i <= j) { if (ai <= (ai = a[i + 1]) && ai <= (ai = a[i + 2])) i += 2; else lock (_locker) b = false; } else while (b && i >= j) { if (ai >= (ai = a[i - 1]) && ai >= (ai = a[i - 2])) i -= 2; else lock (_locker) b = false; } }); return b; }
1,000,000件物品？
if (k < 2) while (b && i < j) if (ai <= (ai = a[i + 1]) && ai <= (ai = a[i + 2]) && ai <= (ai = a[i + 3]) && ai <= (ai = a[i + 4])) i += 4; else lock (_locker) b = false; else while (b && i > j) if (ai >= (ai = a[i - 1]) && ai >= (ai = a[i - 2]) && ai >= (ai = a[i - 3]) && ai >= (ai = a[i - 4])) i -= 4; else lock (_locker) b = false;
让我们忘记百分比。
原件：0.77 ns /项，现在：0.22 ns /项。
2,000,000件物品？ 四核：快4倍。
Linq解决方案。
public static bool IsSorted(IEnumerable list) where T:IComparable { var y = list.First(); return list.Skip(1).All(x => { bool b = y.CompareTo(x) < 0; y = x; return b; }); }
我能想到的唯一改进是同时检查arrays的两端，这个小改动将在半场时间内完成……
public static bool IsSorted(int[] arr) { int l = arr.Length; for (int i = 1; i < l/2 + 1 ; i++) { if (arr[i - 1] > arr[i] || arr[li] < arr[li-1]) { return false; } } return true; }
这可能不是最快的，但它是完整的解决方案。 索引低于i的每个值都将根据i的当前值进行检查。 这是用PHP编写的，但很容易翻译成c＃或javascript
for ($i = 1; $i < $tot; $i++) { for ($j = 0; $j <= $i; $j++) { //Check all previous values with indexes lower than $i if ($chekASCSort[$i - $j] > $chekASCSort[$i]) { return false; } } }
这就是我提出的并且发现更好的工作，特别是对于更大尺寸的arrays。 该函数是递归的，并且将在第一次调用，比如在这样的while循环中
while( isSorted( yourArray, 0 )
if语句检查是否已达到数组的边界。
else if语句将以递归方式调用自身，并在条件变为false时随时中断
public static bool IsSorted(int[] arr, int index) { if (index >= arr.Length - 1) { return true; } else if ((arr[index] <= arr[ index + 1]) && IsSorted(arr, index + 1)) { return true; } else { return false; } }
我想到的问题是“为什么”？
是否要避免重新排序已排序的列表？ 如果是，只需使用Timsort（Python和Java标准）。 利用已经排序或几乎排序的数组/列表非常好。 尽管Timsort在这方面有多好，但最好不要在循环中排序。
另一种方法是使用天生排序的数据结构，如treap，红黑树或AVL树。 这些是在循环内进行排序的好方法。