证明或反驳：有一种一般分类算法可以排序 如果阵列是最小排序的，则
O(n)中的长度为n。
明天我写考试，非常害怕证明任务...这是我从较旧的考试中找到的，非常难以解决……：/
我想我知道答案，但是我的理由不好。因此，我的原因是陈述是错误的，因为当数组是最小的订购时，让它想象为树，那么树的叶子就不会被排序。在O(n)中对该数组进行排序是必需的。因此，语句是错误的。
在这里，我有例子，我自己做自己的小屋顶订购的树：
1
/
3 2
/
8 99 7
从中我们制作数组，我们有1, 3, 2, 8, 99, 7，您发现这根本没有分类。无法在O(n)中进行排序。
非常确定我的解决方案是错误的，您能告诉我您如何正确做到这一点，对我的英语感到非常抱歉，我尽力而为。
我认为我的解决方案是错过的，我需要证明，千里订购的叶子没有排序的叶子？但是如何？
此解决方案是正确的。您可以通过使用假设的排序算法生成线性的一般分类算法来产生正式的证明 varducio ad as assurdum （还原为矛盾）。
对数组A排序的线性时间算法包括通过以小于 min(A)的整数序列开始构建堆有序的数组，然后在末端添加A。该新数组的总长度为O(|A|)-堆的标准数组表示形式，您需要2个元素的下一个较大功率，最多是3·|A|。然后，您可以使用线性时间算法对堆有序的数组进行排序以对此新数组进行排序，最后删除预删除的序列以分类顺序生成原始数组。
由于这与已知的线性一般分类相矛盾，因此我们可以得出结论，没有线性时间算法用于对堆有序的阵列进行排序。
这种问题的通常证明是减少了您的一些知名问题。也就是说，您证明，如果有可能在线性时间解决您的问题，那么也可以在线性时间内解决一些问题X。但是众所周知，x在线性时间无法解决，因此，由于矛盾，您的问题也不那么。
x正在分类的一个很好的例子。众所周知，不可能在Omega(n log n)时间中对n个元素进行排序（Omega这是处理下限的适当方法，请参阅此处）。
现在请注意，如果我们：
- 从n个元素中制作一个heap
- 从Min-Heap Order排序n元素
然后，我们从头开始有效地对这些元素进行分类。因此，这两个步骤中的任何一个至少需要n log n时间。存在一种算法来执行线性时间的第一步（可能在您的教科书中），从而为我们提供了第二步的Omega(n log n)下限，q.e.d。