首先，我知道
我同意下限应该是 O(nlogn)。
我不太明白的是：
对于某些特殊情况，比较次数实际上甚至可能低于下限。例如，使用冒泡排序对已排序的数组进行排序。比较次数为 O(n)。
那么如何真正理解下界的概念呢？
维基百科上的经典定义：http ://en.wikipedia.org/wiki/Upper_and_lower_bounds没有多大帮助。
我目前对此的理解是：
基于比较的排序的下限实际上是最坏情况的上限。
即，在最坏的情况下你能做到什么程度。
这个对吗？谢谢。
基于比较的排序的下限实际上是最佳情况的上限。
您要限制的函数是最佳排序算法的最坏情况运行时间。
想象一下下面的游戏：
O(n log n) 上限意味着您可以将成本限制在最多 O(n log n) 美元，无论我选择什么输入序列。
Ω(n log n) 下限意味着我可以强制你至少支付 Ω(n log n) 美元，无论你选择哪种排序算法。
另外： “下限是 O(n log n)”没有任何意义。O(f(n)) 的意思是“至多是 f(n) 的常数倍”。但是“下限”的意思是“至少……”。所以说“O(n log n) 的下限”就像说“你最多可以节省50 %或更多！” ——完全没有意义！下界的正确表示法是 Ω(...)。
排序问题可以看如下。
输入： n 个数字的序列。输出：输入序列的排列（重新排序），使得 a'1 <= a'2 ..... <= a'n。
如果排序算法使用比较运算符来查找两个数字之间的顺序，则它是基于比较的。可以根据决策树抽象地查看比较排序。决策树是一棵完整的二叉树，它表示由特定排序算法对给定大小的输入执行的元素之间的比较。排序算法的执行对应于跟踪从决策树的根到叶子的路径。在每个内部节点，进行比较ai aj。然后左子树指示 ai aj 的后续比较，右子树指示 ai > aj 的后续比较。当我们来到一片叶子时，排序算法已经建立了排序。所以我们可以说下面的决策树。
1) 每一个 n! n 个元素的排列必须作为决策树的叶子之一出现，以便排序算法正确排序。
2) 令 x 为排序算法中的最大比较次数。决策树的最大高度为 x。最大高度 x 的树最多有 2^x 个叶子。
结合以上两个事实，我们得到以下关系。
n! <= 2^x
两边取Log。\log_2n！<= x
由于 \log_2n! = \Theta(nLogn)，我们可以说 x = \Omega(nLog_2n) 因此，任何基于比较的排序算法都必须至少进行 \Omega(nLog_2n) 比较才能对输入数组进行排序，并且堆排序和归并排序是渐近最优的比较排序.
想象一下可以排序的所有可能的事物数组。可以说它们是长度为“n”的数组，并忽略诸如具有一个元素的数组之类的东西（当然，它们总是已经排序。
想象一下该数组的所有可能值组合的长列表。请注意，我们可以稍微简化一下，因为数组中的值总是有某种排序。因此，如果我们用数字 1 替换最小的一个，用 1 或 2 替换下一个（取决于它是否相等或更大）等等，我们最终会遇到相同的排序问题，就好像我们允许任何值一样。（这意味着长度为 n 的数组最多需要数字 1-n。如果一些相等，可能会更少。）
然后在每个数字旁边放一个数字，说明用其中的值对该数组进行排序需要多少工作。你可以放几个数字。例如，您可以输入所需的比较次数。或者，您可以输入所需的元素移动或交换次数。无论你放什么数字都表明它需要多少次操作。你可以把它们加起来。
您必须做的一件事是忽略任何特殊信息。例如，您无法提前知道数组中值的排列是否已经排序。您的算法必须对该数组执行与任何其他数组相同的步骤。（但第一步可能是检查它是否已排序。不过，通常这对排序没有帮助。）
所以。通过比较测量的最大数字是当值以病态错误方式排列时的典型比较次数。同样，最小的数字是当值以非常好的方式排列时所需的比较次数。
对于冒泡排序，最好的情况（最短或最快）是值是否已经有序。但这只有在您使用标志来判断您是否交换了任何值时。在最好的情况下，您查看每对相邻的元素一次，发现它们已经排序，当您到达最后时，您发现您没有交换任何东西，所以您已经完成了。这是总共 n-1 次比较，是您可以进行的最少比较次数。
我需要一段时间才能弄清楚最坏的情况。几十年来我没有看过冒泡排序。但我猜这是他们被逆序排列的情况。您进行第一次比较并发现第一个元素需要移动。与每个元素相比，您向上滑动到顶部，最后将其与最后一个元素交换。因此，您在那一关中进行了 n-1 次比较。第二遍从第二个元素开始，进行 n-2 次比较，依此类推。因此，在这种情况下，您进行 (n-1)+(n-2)+(n-3)+...+1 比较，大约为 (n**2)/2。
也许您对冒泡排序的变体比我描述的要好。不管。
那么对于冒泡排序，下限为 n-1，上限为 (n**2)/2
其他排序算法有更好的性能。
您可能要记住，除了比较之外，还有其他操作需要花费。我们使用比较是因为很多排序都是用字符串完成的，而且字符串比较在计算时间上是昂贵的。
您可以使用元素交换来计数（或交换和元素交换的总和），但它们通常比与字符串的比较短。如果你有数字，它们是相似的。
您还可以使用更深奥的东西，例如分支预测失败或内存缓存未命中或进行测量。
当您进行渐近分析时，您会为所有输入O推导出一个orΘ或。
但是你也可以分析输入的属性是否影响运行时。
例如，由于输入特征和算法的结构，将几乎排序的东西作为输入的算法比形式渐近公式具有更好的性能。例如冒泡排序和快速排序。
并不是说你可以低于下限。它仅在特定输入上执行的行为。Ω