考虑到从一个非常大的函数返回的数组.
测试数组排序最快的方法是什么？
最简单的方法是：
/// <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)方法与获取的方法相同,没有任何关于阵列可能状态的特殊知识.
您的代码专门测试数组是否以较小的索引较小的值进行排序.如果这不是你想要的,那么如果变得稍微复杂一些.你的代码评论确实表明这是你以后的.
如果您有对可能状态的专门知识(比如,您知道它通常被排序,但最终可能会添加新的数据),则可以优化访问数组元素的顺序,以使测试在数组未排序.
您可以利用硬件体系结构的知识,通过分区阵列来并行检查数组的多个部分,首先比较分区的边界(快速检查失败),然后在单独的线程上运行每个核心的一个数组分区(不超过每个cpu核心1个线程).请注意,如果数组分区远小于高速缓存行的大小,线程将趋向于相互竞争,以访问包含数组的内存.多线程对于相当大的数组将是非常有效的.
