考虑有一个非常大的数组从一个函数返回。
如何最快速地测试数组是否已排序？
最简单的方法是：
/// <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个线程）。请注意，如果数组分区比缓存行的大小小得多，则线程将相互竞争以访问包含数组的内存。对于相当大的数组，多线程才能非常高效。
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架构。四核线程。 一个包含十万个元素的已排序数组：约为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;
}
100万个物品？
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纳秒，现在：每个项目0.22纳秒。
200万个项目？四个核心：速度提高4倍。
ai <= (ai = a[i])（以及类似的内容）。） - greybeardvolatile 或 Thread.MemoryBarrier 就足够了。实际上，在某个线程已经将 false 设置后读取 true 不会导致算法给出错误的结果，并且这可能是不需要特定顺序的良好权衡。 - StevesLinq解决方案。
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;
});
}
What will be the fastest approach to test if the array is sorted?. This solution is at best as fast as the OP's solution, and is probably a little slower. Linq may be the new black, but it's not the best solution all of the time.翻译：楼主问：“如何最快地测试数组是否已排序？” 这个解决方案最快与楼主的方案速度相当，甚至可能稍微慢一些。Linq也许是新宠，但它并不总是最佳解决方案。 - Eric J.这是我的函数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;
}
这是我想出来的，而且发现在处理更大的数组时效果更好。该函数是递归的，并且将在第一次调用时被调用，比如在一个 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;
}
}
如果顺序不重要（降序或升序）。
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;
}
这可能不是最快的解决方案，但它是完整的解决方案。每个具有小于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;
}
}
}
tot的增长，比较次数的渐近增长阶。利用顺序关系具有传递性的机会是否存在？ - greybeard