考虑到从一个非常大的函数返回的数组。
fastest测试数组是否已排序的方法是什么？
一个最简单的方法是：
/// <summary>
/// Determines if int array is sorted from 0 -> Max
/// </summary>
public static bool IsSorted(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
if (arr[i - 1] > arr[i])
{
return false;
}
}
return true;
}
您将不得不访问数组的每个元素以查看是否有任何未排序的元素。
您的 O(n) 方法几乎与它一样快，没有任何关于数组可能状态的特殊知识。
您的代码专门测试数组是否在较低的索引处使用较小的值进行排序。如果这不是您想要的，那么您的if会变得稍微复杂一些。您的代码注释确实表明这就是您所追求的。
如果您对可能的状态有特殊的了解（例如，您知道它通常已排序但新数据可能会添加到末尾），您可以优化访问数组元素的顺序，以允许测试在数组未排序。
您可以利用硬件架构知识通过对阵列进行分区来并行检查阵列的多个部分，首先比较分区的边界（快速检查失败），然后在单独的线程上为每个内核运行一个阵列分区（不超过每个 CPU 内核 1 个线程）。请注意，如果数组分区远小于缓存行的大小，线程将倾向于相互竞争以访问包含数组的内存。多线程只会对相当大的数组非常有效。
更快的方法，平台目标：任何 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，相同的阵列：快约 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;
}
测量它（见灰胡子的评论）。
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/item，现在：0.22 ns/item。
2,000,000 件物品？四核：快 4 倍。
林克解决方案。
public static bool IsSorted<T>(IEnumerable<T> list) where T:IComparable<T>
{
var y = list.First();
return list.Skip(1).All(x =>
{
bool b = y.CompareTo(x) < 0;
y = x;
return b;
});
}
这是我的函数 IsSorted 的版本
public static bool IsSorted(int[] arr)
{
int last = arr.Length - 1;
if (last < 1) return true;
int i = 0;
while(i < last && arr[i] <= arr[i + 1])
i++;
return i == last;
}
虽然这个函数比问题中的要快一点，但它所做的分配和比较比迄今为止发布的任何东西都要少。在最坏的情况下，它会进行 2n+1 次比较。如果您可以对数据的性质做出合理的假设，例如最小数据大小或数组包含偶数个元素，它仍然可以改进。
我能想到的唯一改进是同时检查数组的两端，这个小小的改变将在一半时间内完成......
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[l-i] < arr[l-i-1])
{
return false;
}
}
return true;
}
如果顺序无关紧要（降序或升序）。
private bool IsSorted<T>(T[] values) where T:IComparable<T>
{
if (values == null || values.Length == 0) return true;
int sortOrder = 0;
for (int i = 0; i < values.Length - 1; i++)
{
int newSortOrder = values[i].CompareTo(values[i + 1]);
if (sortOrder == 0) sortOrder = newSortOrder;
if (newSortOrder != 0 && sortOrder != newSortOrder) return false;
}
return true;
}
这就是我想出的，并且发现效果更好，特别是对于更大尺寸的数组。该函数是递归的，将在第一次调用，比如在这样的 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树。这些是在循环内排序的好方法。
这可能不是最快的，但它是完整的解决方案。索引低于 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;
}
}
}