我已经读过这篇文章，但答案并不让我满意。检查Array是否在Log(N)中排序。
想象一下，我有一个超过1000000个double数字(正数和/或负数)的大数组，我想知道这个数组是否经过了"排序"，试图避免比较的最大数量，因为比较双精度和浮点值需要太多时间。有可能对它使用统计数据吗？，如果是：
- 它被真正的程序员看到了吗
- 我应该取样吗
- 我应该拿多少样品
- 它们应该是随机的，还是按顺序排列
- 允许说
"the array sorted"的%误差是多少
谢谢。
这取决于您的需求。如果你可以说，如果1.000.000中的100个随机样本就足够了，那么假设它是排序的-那么它就是这样。但要绝对确定的是，你必须仔细检查每一个条目。只有你才能回答这个问题，因为只有你知道你需要对它的排序有多确定。
这是高中教的一个经典概率问题。考虑这个问题：
批次被拒绝的概率是多少？在一批8000个时钟中，有7%是有缺陷的。从8000个样本中随机抽取10个样本(不替换)进行测试。如果至少有一个有缺陷，整个批次将被拒收。
因此，您可以从大数组中随机抽取一些样本，看看它是否已排序，但您必须注意，您需要知道样本无序的概率。由于你没有这些信息，概率方法在这里不会有效地工作。
(然而，你可以检查50%的数组，并天真地得出结论，它有50%的机会被正确排序。)
如果使用多处理运行分治算法(真正的并行性，因此仅适用于多核CPU)，则可以在Log(N)中检查数组是否排序。
如果你有GPU多处理，你可以很容易地实现Log(N)，因为现代显卡能够并行运行数千个进程。
您的问题5是您需要回答的问题，以确定其他答案。为了确保数组得到完美排序，您必须遍历每个元素，因为其中任何一个元素都可能是不合适的。
决定数组是否排序的最大比较次数为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[I+1])。
现在这似乎很简单：最初的误差是1/2^N。在第一次比较之后，一半可能的组合(全部未排序)被排除。所以错误率应该是1/2^n+1/2^(n-1)。
我不是数学家，但计算需要多少元素才能达到错误率应该很容易(找到x，使得error>=1/2^n+1/2^(n-1)的和。。。1/^(2-x))
对不起，我的英语搞糊涂了。我来自德国。。
由于每个元素都可能是一个越界的元素，因此必须遍历所有元素，因此您的算法具有运行时O(n)。
如果你对"排序"的理解不那么严格，你需要说明你所说的"排序"是什么意思。通常，"排序"意味着相邻元素满足一个或多或少或相等的条件。
就像其他人所说的那样，100%确保排序的唯一方法是遍历每一个元素，即O(N)。
然而，在我看来，如果你非常担心它被排序，那么也许从一开始就对它进行排序比将数组元素存储在内存中的连续部分更重要？
我的意思是，你可以使用一个映射，它的元素根据定义遵循严格的弱排序。换句话说，映射中的元素总是经过排序的。您也可以使用一个集合来实现相同的效果。
例如：std::map<int,double> collectoin;将允许您几乎像使用数组一样使用它：collection[0]=3.0; std::cout<<collection[0]<<std:;endl;。当然也有区别，但如果排序如此重要，那么数组是存储数据的错误选择。
旧的时尚方式。把它打印出来，看看那里是否整齐。真的，如果你的分类是错误的，你可能很快就会看到。如果你对100多件东西进行排序，那么你不太可能只看到几个错误的订单。当我处理它的时候，我的整个事情都是完全不正常的，或者它是有效的。
作为一个可能不应该使用但演示采样大小的示例：
统计上有效的样本量可以给你一个合理的排序估计。如果你想95%地确定每件事都是排序的，你可以通过创建一个真正随机的采样点列表来做到这一点，也许是1500个。
从本质上讲，如果一个地方的值列表无序，将破坏后续算法或数据需求，那么这是完全没有意义的。
如果这是一个问题，请在代码运行之前对列表进行预处理，或者在代码中使用一个非常快速的排序包。大多数排序包也有一个验证模式，它只是简单地告诉你是的，列表是否符合你的排序标准。其他的建议，比如用线程并行化检查，都是不错的主意。