c# – 检查数组是否排序的最快方法

发布时间：2020-12-15 04:23:16 所属栏目：百科来源：网络整理

导读：考虑到从一个非常大的函数返回的数组. 测试数组排序最快的方法是什么？最简单的方法是： /// summary/// Determines if int array is sorted from 0 - Max/// /summarypublic static bool IsSorted(int[] arr){for (int i = 1; i arr.Length; i++){ if (arr

考虑到从一个非常大的函数返回的数组.

测试数组排序最快的方法是什么？

最简单的方法是：

/// <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个线程).请注意,如果数组分区远小于高速缓存行的大小,线程将趋向于相互竞争,以访问包含数组的内存.多线程对于相当大的数组将是非常有效的.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!