我已经阅读了这篇文章，但答案并不满意Check if Array is sorted in Log(N)。
想象一下，我有一个超过 1,000,000 个double数字（正数和/或负数）的大型数组，我想知道数组是否已“排序”，试图避免最大比较次数，因为比较双精度数和浮点数需要太多时间。是否可以对它使用统计信息？如果它是：
"the array sorted"多少？谢谢。
这取决于您的要求。如果您可以说如果 1.000.000 中的 100 个随机样本就足够了，那么假设它已排序 - 那么就是这样。但可以肯定的是，您将始终必须检查每一个条目。只有您可以回答这个问题，因为只有您知道您需要对它进行排序有多确定。
这是高中教授的经典概率问题。考虑这个问题：
批次被拒绝的概率是多少？在 8,000 个批次中，有 7% 的时钟有缺陷。从 8,000 个中随机抽取 10 个（无替换）样本并进行测试。如果至少有一个有缺陷，则整个批次将被拒绝。
所以你可以从你的大数组中随机抽取一些样本，看看它是否排序，但你必须注意，你需要知道样本乱序的概率。由于您没有该信息，因此概率方法在这里不会有效。
（但是，您可以检查 50% 的数组并天真地得出结论，它有 50% 的机会正确排序。）
决定数组是否排序的最大比较次数是N-1，因为有N-1个相邻的数对要比较。但为简单起见，我们会说 N，因为我们看 N 或 N+1 个数字并不重要。
此外，从哪里开始并不重要，所以让我们从头开始。比较#1（A[0] 与 A[1]）。如果失败，则数组未排序。如果成功了，很好。
正如我们只比较，我们可以将其减少到邻居以及左侧是否小于或等于（1）或不（0）。所以我们可以把数组看成一个0和1的序列，表示两个相邻的数字是否有序。
计算错误率或概率（正确拼写？）我们将不得不查看 0/1 序列的所有组合。我会这样看：我们有一个数组的 2^n 个组合（即对的顺序，其中只有一个被排序（所有元素都是 1，表示每个 A[i] 小于或等于 A[我+1]）。
现在这似乎很简单：最初的错误是 1/2^N。在第一次比较之后，可能的组合（所有未排序）的一半被淘汰。所以错误率应该是1/2^n + 1/2^(n-1)。
我不是数学家，但计算达到错误率需要多少元素应该很容易（找到 x 使得 ERROR >= sum of 1/2^n + 1/2^(n-1) ... 1/^(2-x) )
对不起，令人困惑的英语。我来自德国。。
如果您使用多处理运行分治算法（真正的并行性，因此仅适用于多核 CPU），您可以检查数组是否在 Log(N) 中排序。
如果你有 GPU 多处理，你可以很容易地实现 Log(N)，因为现代显卡能够并行运行数千个进程。
您的问题 5 是您需要回答以确定其他答案的问题。为确保数组完美排序，您必须遍历每个元素，因为其中任何一个元素都可能不合适。
作为示例，您可能不应该使用但演示了采样大小：
统计上有效的样本量可以为您提供合理的排序估计。如果您想 95% 确定 eerything 已排序，您可以通过创建一个真正随机的采样点列表来做到这一点，可能约为 1500。
从本质上讲，如果在一个地方出现乱序的值列表会破坏后续算法或数据要求，那么这完全没有意义。
如果这是一个问题，请在代码运行之前对列表进行预处理，或者在代码中使用非常快速的排序包。大多数排序包也有一个验证模式，它只是告诉你是，列表符合你的排序标准 - 或不。其他建议，例如使用线程并行化检查是个好主意。
由于每一个元素都可能是一个不合规的元素，因此您必须遍历所有元素，因此您的算法的运行时间为 O(n)。
如果您对“排序”的理解不那么严格，则需要指定“排序”的含义。通常，“排序”意味着相邻元素满足更少或更少或相等的条件。
就像其他人所说的那样，100% 确定它已排序的唯一方法是遍历每个元素，即 O(N)。
但是，在我看来，如果您非常担心它会被排序，那么也许从一开始就对其进行排序比将数组元素存储在内存中的连续部分中更重要？
我要说的是，您可以使用一个地图，其元素根据定义遵循严格的弱排序。换句话说，地图中的元素总是被排序的。您也可以使用一组来达到相同的效果。
例如：std::map<int,double> collectoin;将允许您几乎像数组一样使用它：collection[0]=3.0; std::cout<<collection[0]<<std:;endl;。当然存在差异，但如果排序如此重要，那么数组是存储数据的错误选择。
老式的方式。打印出来看看是否有顺序。真的，如果你的排序是错误的，你可能很快就会看到它。如果您对 100 多件物品进行分类，则不太可能只看到一些错误。每当我处理它时，我的整个事情都完全关闭或者它起作用了。