《算法技术手册》分析技术

讨论排序时，肯定得分析一个算法在最好情况、最坏情况和平均情况下的性能（在第2章中讨论过）。平均情况的性能分析一般是最难进行准确量化分析的，而且需要高级的数学技巧。一个合理的可能性理解是，我们假设输入也许是部分有序的。即便是当一个算法在平均情况下已经被认为有一个令人满意的表现时，它却可能不那么适合于实际应用。对于本章中的每个排序算法，我们都分析了它们的理论性能和实践中的真实性能。

计算机科学中的一个基本结论是：无论是在平均情况还是在最坏情况下，一个基于比较的排序算法不可能得到比O(n log n)更快的性能。我们现在简要地证明一下这个结论。给定n个元素，有n!种排列。每个使用两两比较的排序算法都相当于下面的二叉决策树。决策树的叶子就相当于下面的一个排列，每个排列至少在树中与一个叶子相对应。每条路径从根到叶子上的节点就相当于一个比较序列。这棵树的高度就是从根到叶子的最长路径上的比较节点的数目，例如，图4-5中的树的高度就是5，因为在所有的情况下，五次比较是必需的（虽然在四种情况下只需要四次比较）。

构建一个二叉决策树，使得每个内部节点表示一个ai≤aj的比较行为，叶子表示n!的一个排列。对一个含有n个元素的集合进行排序，从根节点开始向下遍历，对在每一个节点中的表达式进行求值。如果表达式为真则向左遍历，否则向右遍历。图4-5表示了一个有四个元素的决策树。

一个数据集合可以构造大量的二叉决策树。即便这样，我们给定任意一个对n个元素进行比较的二叉决策树，我们都能够计算它的最小高度，也就是说，肯定存在含有一些叶子节点，从根节点到达这些叶子节点只需要经过h个比较节点。考虑一个高度为h的完全二叉树，这棵树所有的非叶节点都有左右子节点。这棵树总共包括n=2h-1个节点，高度h为log(n+1)。如果这棵树不是完全二叉树的话，也许在某些特殊情况下并是不平衡的。但是我们知道h≥log(n+1)[1]。已经证明了任何具有n!个叶子节点的二叉决策树最少含有n!个节点。我们只需要按照h=log(n!)来计算任何一个二叉决策树的高度即可。在这里，我们利用了对数的如下性质：log(a*b)=log(a)+log(b)和log(xy)=y*log(x)。

h=log(n!)=log(n*(n-1)*(n-2)*……*2*1)

h＞log(n*(n-1)*(n-2)*……*n/2)

h＞log((n/2)n/2)

h＞(n/2)*log(n/2)

h＞(n/2)*(log(n)-1)

因此h＞(n/2)*(log(n)-1)。这个公式的含义是什么？给定n个元素对其进行排序，那么至少存在一条路径从根到叶子，路径长度为h，也就是说，这个算法在排序的过程中进行至少需要h次比较。注意h是由一个函数f(n)计算出来的，尤其在这里，f(n)=(1/2)*n*log(n)-n/2，表示任何基于比较的排序算法至少需要大约O(n log n)次比较进行排序。在下面的章节“桶排序”中，我们将会看到一种不一样的算法，这种算法并不完全是基于元素之间的比较，因此在某些特殊条件下能得到比较好的性能表现。