基本上所有像样的算法教科书都解释了像快速排序和堆排序这样的排序算法有多快，但不需要复杂的数学它只是表明你可以逐渐接近多快。关于符号的重要说明：大多数计算机科学家使用大写O符号来表示“接近直到达到恒定比例因子”，这与数学专业的意思不同。我在这里使用的大O符号与计算机教科书所指的含义相同，但至少不会与其他数学符号混合使用。基于比较的排序我们先来看一个特例，即一次比较两个值大小的算法（快速排序、堆排序等一般排序算法）。这个想法随后可以扩展到所有排序算法。一个简单的最坏情况的计数角度假设有4个互不相等的数字随机排列，只比较一对数字是否可以排序？显然不是，证明如下：根据定义，要对这个数组进行排序，需要按某种顺序重新排列数字。换句话说，您需要知道要使用哪种排列吗？有多少种可能的排列？第一个数可以放在四个位置中的任意一个，第二个数可以放在剩余三个位置中的任意一个，第三个数可以放在剩余两个位置中的任意一个，最后只剩下一个位置为一个号码。这样就有4×3×2×1=4!=24种排列可供选择。通过一次大小比较，只有两种可能的结果。如果列出所有的排列，那么“从小到大”排序可能对应第8个排列，“从大到小”排序可能对应第24个排列，但无法知道其他22个什么时候需要种的排列。2次比较，有2×2=4种可能的结果，还是不够。只要比较次数少于5次（对应25=32次输出），4个数随机排序的排序就做不到。如果W(N)是在最坏情况下对N个不同元素进行排序所需的比较次数，则两边以2为底取对数，得到：N！增长大约为NN（参见斯特林公式），嗯，从输出计数的角度来看，这是最坏情况下的O(NlogN)上限。信息论视角下的平均状态示例利用信息论的一些知识，可以从上述讨论中得出更有力的结论。接下来，使用排序算法作为信息传递的编码器：取任意一个数，比如15从4个数的排列列表中找到第15个排列，在这个排列上运行排序算法，记录所有“大”和“小”的比较结果以二进制码发送接收方逐步重新执行发送方的排序算法，必要时可以参考发送方的比较结果现在接收方可以知道发送方是如何重新排列数字以按需要排序的，接收方可以反转排列，得到4个数字的初始序列接收方在排列表中检索发送方的原始排列，并表明发送方发送了15。是的，这有点奇怪，但它有效。这意味着排序算法遵循与编码方案相同的法则，包括理论上证明不存在通用数据压缩算法。在该算法中，每次比较都发送1比特的比较结果编码数据。根据信息论，比较的次数至少是能表示所有数据的二进制位数。在更技术性的说明中，平均所需的最少比较次数是输入数据的香农熵，以位为单位。熵是对信息等不可预测量的数学度量。对于一个N个元素的数组，当元素的排列顺序随机无偏时，熵最大，其值为log2N！位。这证明O(NlogN)是基于比较对任意输入进行排序的最佳平均值。以上是理论上的说法，那么实际的排序算法如何比较呢？下面是对数组进行排序所需的平均比较次数的图表。我正在将理论值与快速排序和Ford-Johnson合并插入排序的性能进行比较。后者旨在最小化比较次数（总体上并不比快速排序快多少，因为生活中还有比最小化比较次数更重要的事情）。并且因为合并-插入排序在1959年被提出，所以进行了调整，减少了比较次数，但是图示说明基本达到了最优状态。一点理论就能得出如此实用的结论，感觉真好！总结证明：如果数组可以任意排序，最坏情况下至少需要O(NlogN)次比较。数组的最小平均比较次数是数组的熵，对于随机输入是O(NlogN)。请注意，第二个结论允许基于比较的算法优于O(NlogN)，前提是输入是低熵（换句话说，部分可预测）。如果输入包含许多已排序的子序列，则归并排序的性能接近于O(N)。如果在确定位之前对其输入进行排序，则插入排序性能接近于O(N)。在最坏的情况下，上述算法的性能不会超过O(NlogN)。一般排序算法中基于比较的排序在实践中是一个有趣的特例，但理论上计算机的CMP指令与其他指令相比并没有什么特别之处。前两种情况可以在以下两种的基础上扩展为任意排序算法：大多数计算机指令有两个以上的输出，但输出的数量仍然有限。一条指令的有限输出意味着一条指令只能处理有限数量的熵。这给出了对应于O(NlogN)的指令的下限。任何物理上可实现的计算机在给定时间只能执行有限数量的指令，因此算法的执行时间也有对应于O(NlogN)的下限。什么是更快的算法？一般意义上的O(NlogN)的下限，在实践中，如果你听到任何更快的算法，你必须知道它一定是在某种程度上“作弊”，并且一定有陷阱，即它不是可以处理任意大数组的通用排序算法。它可能是一种有用的算法，但最好从字里行间中读出。一个著名的例子是基数排序算法，它通常被称为O(N)排序算法，但它只能处理所有数字都适合k位的情况，所以实际上它的性能是O(kN).这意味着什么？如果使用8位计算机，那么8个二进制位可以表示28=256个不同的数。如果数组有几千个数字，那么一定有重复。这对于某些应用程序来说很好，但对于其他应用程序来说，它必须用16个二进制位来表示，这可以表示216=65,536个不同的数字。32个二进制位可以表示232=4,294,967,296个不同的数。随着数组长度的增长，所需的位数也随之增长。要表示N个不同的数字，需要k≥log2N个二进制位。因此，仅当数组中允许重复数字时，O(kN)优于O(NlogN)。一般来说，输入数据的O(NlogN)性能已经说明了所有问题。这个讨论没有那么有趣，因为很少需要在32位计算机上对数十亿整数进行排序，而且如果任何人的需求超过了64位计算机的限制，他一定不能告诉别人。
